Indexed text attachment
entropy-sources-and-channels-in-higher-categories.tex
Source for Entropy, Sources, and Channels in Higher Categories
View paper · Download original file
Lines 2089–2188 of 4249. Source text is displayed literally.
2089\end{exercise}2090 2091\begin{exercise}2092On $[0,1)$ with Lebesgue measure let $\FF_n$ be generated by the dyadic intervals of length $2^{-n}$ and let2093$f(x)=x$. Compute $\E[f\st\FF_n]$ and show that $\|f-\E[f\st\FF_n]\|_2=2^{-n}/\sqrt{12}$.2094\end{exercise}2095 2096\begin{exercise}\label{exer:likelihood}2097Let $x_1,x_2,\dots$ be fair coin tosses and $M_n=\prod_{k\le n}2\theta^{x_k}(1-\theta)^{1-x_k}$ with $\theta=0.8$. Show that2098$M_n$ is a martingale with $\E M_n=1$ and that $\E\sqrt{M_n}=\rho^n$ with2099$\rho=\tfrac12(\sqrt{1.6}+\sqrt{0.4})\approx0.949$. Deduce that $M_n\to0$ in probability and that $M_n$ is not2100closed.2101\end{exercise}2102 2103\begin{exercise}2104Let $U$ be the permutation matrix of $\sigma=(1\,2\,3)(4\,5)$ acting on functions on $\{1,\dots,5\}$. Compute2105$\frac16\sum_{k<6}U^k$ and identify it with a conditional expectation.2106\end{exercise}2107%% ---- end ch/07-martingales.tex ----2108%% ---- begin ch/08-aep.tex ----2109\chapter{McMillan's Theorem}\label{ch:aep}2110 2111McMillan's theorem says that for an ergodic source almost all long blocks have about the same probability,2112$2^{-nH}$. Shannon proved it for independent letters and for Markov chains, where it is the law of large2113numbers, and Khinchin's first paper follows him. The general case is due to McMillan, and proving it2114carefully is the main task of the second chapter of Khinchin's second paper, which takes some thirty pages2115and rests on the theorems of Birkhoff and Doob. With the preparation of the last two chapters the proof is2116short, and it shows what the theorem depends on: the chain rule, two convergence statements about2117idempotents, and one elementary estimate.2118 2119\section{The statement}2120 2121For a stationary source $\mu$ and $n\ge1$ let2122\[ i_n(x)=-\log\mu_n(x_0\dots x_{n-1}) \]2123be the \term{information} of the first $n$ letters. Its expectation is the block entropy $H_n$.2124 2125\begin{definition}[Khinchin]2126A source has the \term{$E$ property} if $\frac1ni_n\to H(\mu)$ in probability: for all $\varepsilon,\delta>0$2127and all large $n$, the blocks $C$ of length $n$ with $|-\frac1n\log\mu_n(C)-H(\mu)|\le\varepsilon$ have total2128probability more than $1-\delta$.2129\end{definition}2130 2131\begin{theorem}[McMillan]\label{thm:mcmillan}2132\Scl[\cite{McM53,Khi56}] For an ergodic source, $\frac1ni_n\to H(\mu)$ in $L^1(\mu)$. In particular every ergodic2133source has the $E$ property. For a stationary source, $\frac1ni_n$ converges in $L^1$ to the entropy2134$H(\mu_x)$ of the ergodic component of $x$.2135\end{theorem}2136 2137\section{Information as a sum over time}2138 2139Let $\FF_k$ be generated by $x_{-k},\dots,x_{-1}$, with $\FF_0$ trivial and $\FF_\infty$ generated by the whole past.2140For $0\le k\le\infty$ put2141\[ g_k(x)=-\log\mu(x_0\st\FF_k)(x), \]2142the information of the present letter given the last $k$ letters. In the notation of \cref{ch:martingales},2143$g_k=-\log M_k^{x_0}$.2144 2145\begin{lemma}\label{lem:timesum}2146\Scl $i_n=\sum_{k=0}^{n-1}g_k\circ T^k$, and $\E g_k=c_k$, the increment of \cref{prop:rate}.2147\end{lemma}2148 2149\begin{proof}2150$\mu_n(x_0\dots x_{n-1})=\prod_{k<n}\mu(x_k\st x_0,\dots,x_{k-1})$, and by stationarity the $k$-th factor is2151$\mu(x_0\st\FF_k)$ evaluated at $T^kx$.2152\end{proof}2153 2154This is the chain rule of \cref{ch:schemes} spread along the time axis. If the summands were one function2155$g$ composed with the powers of $T$, the ergodic theorem would finish the proof. They are not, but they2156converge.2157 2158\begin{lemma}\label{lem:tail}2159\Scl For every $0\le k\le\infty$ and $t\ge0$,2160\[ \mu\{g_k>t\}\le|A|\,2^{-t}. \]2161Consequently $\sup_k\E[g_k^2]<\infty$, and $\mu(x_0\st\FF_\infty)>0$ almost surely.2162\end{lemma}2163 2164\begin{proof}2165For a letter $a$ and $s=2^{-t}$,2166\[ \mu\{x_0=a,\ M_k^a\le s\}=\E\bigl[1_{\{M_k^a\le s\}}\,\E[1_{\{x_0=a\}}\st\FF_k]\bigr]=\E\bigl[1_{\{M_k^a\le s\}}M_k^a\bigr]\le s. \]2167Sum over $a$. The second moment is $\int_0^\infty2t\,\mu\{g_k>t\}\,dt$.2168\end{proof}2169 2170\begin{lemma}\label{lem:gk}2171\Scl $g_k\to g_\infty$ in $L^1$, and $\E g_\infty=H(\mu)$.2172\end{lemma}2173 2174\begin{proof}2175By \cref{cor:levy}, $M_k^a\to M_\infty^a$ in $L^1$ for each letter, so $M_k^{x_0}\to M_\infty^{x_0}$ in probability. The limit is2176almost surely positive by \cref{lem:tail} and $-\log$ is continuous on $(0,1]$, so $g_k\to g_\infty$ in2177probability. A sequence bounded in $L^2$ is uniformly integrable, so the convergence is in $L^1$. Then2178$\E g_\infty=\lim\E g_k=\lim c_k=H(\mu)$.2179\end{proof}2180 2181\section{Proof of the theorem}2182 2183\begin{proof}[Proof of \cref{thm:mcmillan}]2184Since $T$ preserves $\mu$, \cref{lem:timesum} gives2185\[ \Bigl\|\frac1ni_n-\frac1n\sum_{k<n}g_\infty\circ T^k\Bigr\|_1\le\frac1n\sum_{k<n}\|g_k-g_\infty\|_1, \]2186which tends to zero by \cref{lem:gk}. By the mean ergodic theorem (\cref{cor:meanergodic}),2187$\frac1n\sum_{k<n}g_\infty\circ T^k\to\E[g_\infty\st\II]$ in $L^1$. If $\mu$ is ergodic this is the constant2188$\E g_\infty=H(\mu)$. In general it is an invariant function whose integral over each ergodic component is the