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

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}2201The limit can be written in one line. Let $e_{\mathrm{past}}$ be the idempotent of the $\sigma$-algebra2202generated by the past and $e_\II$ that of the invariant sets. The first determines the conditional law of2203$x_0$ given the past, hence the function $g_\infty$; the second is applied to it:2204\[ \lim_n\tfrac1ni_n=L^1(e_\II)\,g_\infty. \]2205The entropy of an ergodic source is the time average of the information of the present given the past.2206\end{remark}2207 2208\section{The almost sure theorem}2209 2210\begin{theorem}[Shannon--McMillan--Breiman]\label{thm:SMB}2211\Scl[\cite{Bre57,Chu61,AC88}] For an ergodic source, $\frac1ni_n\to H(\mu)$ almost surely. The same holds for2212countable alphabets when $H_1<\infty$.2213\end{theorem}2214 2215Breiman's proof combines the almost sure forms of the two convergence theorems with a maximal inequality2216for $\sup_kg_k$, of which \cref{lem:tail} is the distributional part; Algoet and Cover later gave a proof by2217sandwiching $i_n$ between Markov approximations. The theorem extends to actions of amenable groups2218\cite{OW83,Lin01}. For the coding theorems convergence in probability is all that is needed.2219 2220\section{Typical sets and the counting theorem}2221 2222Fix $\varepsilon>0$ and let $T_n^\varepsilon$ be the set of blocks $C$ of length $n$ with2223$2^{-n(H+\varepsilon)}\le\mu_n(C)\le2^{-n(H-\varepsilon)}$, where $H=H(\mu)$.2224 2225\begin{corollary}\label{cor:typical}2226\Scl For an ergodic source, $\mu_n(T_n^\varepsilon)\to1$; $|T_n^\varepsilon|\le2^{n(H+\varepsilon)}$ for all $n$; and2227$|T_n^\varepsilon|\ge(1-\delta)\,2^{n(H-\varepsilon)}$ as soon as $\mu_n(T_n^\varepsilon)\ge1-\delta$.2228\end{corollary}2229 2230For $0<\lambda<1$ let $N_n(\lambda)$ be the least number of blocks of length $n$ whose total probability is at2231least $\lambda$.2232 2233\begin{theorem}[Khinchin's Theorem 3]\label{thm:counting}2234\Scl[\cite{Sha48,Khi53}] For an ergodic source and every $\lambda\in(0,1)$,2235\[ \lim_{n\to\infty}\frac1n\log N_n(\lambda)=H(\mu). \]2236\end{theorem}2237 2238\begin{proof}2239For large $n$ the typical set has probability at least $\lambda$, so $N_n(\lambda)\le2^{n(H+\varepsilon)}$. Conversely let2240$S$ have probability at least $\lambda$. For large $n$, $\mu_n(S\cap T_n^\varepsilon)\ge\lambda/2$, and each block in2241$T_n^\varepsilon$ has probability at most $2^{-n(H-\varepsilon)}$, so $|S|\ge\frac\lambda2\,2^{n(H-\varepsilon)}$.2242\end{proof}2243 2244The limit does not depend on $\lambda$. That is the remarkable part of the statement, and it is special to2245the ergodic case.2246 2247\begin{example}\label{ex:counting}2248For independent bits with $\Prob(1)=0.2$ the entropy is $\hb(0.2)\approx0.7219$. The typical set with2249$\varepsilon=0.05$ has probability $0.468$ at $n=100$ and $0.952$ at $n=1000$. The rates $\frac1n\log N_n(\lambda)$2250are:2251\begin{center}\small2252\begin{tabular}{@{}lccc@{}}2253\toprule2254 & $\lambda=0.1$ & $\lambda=0.5$ & $\lambda=0.9$\\\midrule2255$n=100$ & $0.571$ & $0.684$ & $0.779$\\2256$n=1000$ & $0.683$ & $0.717$ & $0.748$\\2257\bottomrule2258\end{tabular}2259\end{center}2260The spread across $\lambda$ shrinks like $1/\sqrt n$ (\cref{exer:second}). For the Markov source of