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

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}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}