Independent scholarship · Open accessThe monthly digest

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 2101–2200 of 4249. Source text is displayed literally.

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 the2189entropy of that component.2190\end{proof}2191 2192The argument used four things. The chain rule put $i_n$ in the form of \cref{lem:timesum}. L\'evy's theorem in2193mean, which is the convergence of an increasing sequence of idempotents (\cref{thm:projections}), gave the2194convergence of the conditional laws. The mean ergodic theorem, which is the convergence of time averages to2195the invariant idempotent (\cref{thm:vN}), gave the limit. \Cref{lem:tail} supplied the uniform integrability2196needed to pass from conditional probabilities to their logarithms. Doob's almost sure theorem and2197Birkhoff's were not used. This organization of the proof is certainly known to specialists; we set it out2198because it isolates how little of the measure theory in Khinchin's proof is specific to the problem.2199 2200\begin{remark}\label{rem:twoidem}