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

2049extends to the closure.2050\end{proof}2051 2052\begin{corollary}\label{cor:meanergodic}2053\Scl Let $\mu$ be a stationary source and $f\in L^1(\mu)$. Then $\frac1n\sum_{k<n}f\circ T^k\to\E[f\st\II]$ in $L^1$.2054\end{corollary}2055 2056\begin{proof}2057$Uf=f\circ T$ is an isometry of $L^2(\mu)$ whose invariant vectors are the $\II$-measurable functions. For2058$f\in L^2$ apply \cref{thm:vN}; $L^2$ is dense in $L^1$ and the averages are contractions of $L^1$.2059\end{proof}2060 2061In the language of this chapter the limit is again an idempotent. Let $q\colon X\to X_{\mathrm{inv}}$ be the2062invariant quotient of \cref{thm:MP}. Then $e_\II=q^\dagger\circ q$ is the dagger idempotent of the invariant2063$\sigma$-algebra, and the corollary says that the Ces\`aro averages of the powers of $T$ converge to it2064under $L^1$.2065 2066We now have two convergence statements of the same form. Along a filtration, an increasing sequence of2067idempotents converges to its supremum. Along time, the averages of an automorphism converge to the2068idempotent of its invariants. The first is an instance of \cref{thm:PVB}. The second is not, since the2069averages are not idempotents and do not form a monotone net; whether it has a proof internal to an2070enriched dagger Markov category is a question we return to in \cref{ch:coda}.2071 2072\section*{Notes}2073 2074Khinchin's section on martingales is \cite[\S6]{Khi56}, after Doob \cite{Doo53}. The dagger structure on2075categories of probability spaces is discussed in \cite{CJ19,Fri20,DDGK16}. The treatment of conditional2076expectations as idempotents and \cref{thm:PVB} are due to Perrone and Van Belle \cite{PVB24}; see also Van2077Belle \cite{VB23}. The proof of the mean ergodic theorem given here is F.~Riesz's.2078 2079\section*{Exercises}2080 2081\begin{exercise}2082Let $X=\{1,\dots,6\}$ with the uniform distribution and let $\GG$ be generated by the partition2083$\{1,2\}\,|\,\{3,4,5,6\}$. Write $e_\GG$ as a stochastic matrix, check that it is idempotent and symmetric, and2084compute its action on $f(x)=x$.2085\end{exercise}2086 2087\begin{exercise}2088Prove \cref{prop:idem}(iii). Give two $\sigma$-algebras on a three-point space whose idempotents do not commute.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