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 2021–2120 of 4249. Source text is displayed literally.
2021\begin{proof}2022(i) is the density used in \cref{cor:levy}. (ii) is the definition of a martingale. (iii) is the classical2023fact that for $r>1$ an $L^r$-bounded martingale is closed, with $\|f\|_r=\sup_n\|\E[f\st\FF_n]\|_r$. (iv) On a finite2024$\sigma$-algebra an integrable function is the density of a signed measure, and a martingale is a2025compatible family of signed measures on the algebras of cylinders with bounded total variation, which2026extends uniquely to a signed measure on the sequence space. Closed martingales correspond to measures with a2027density.2028\end{proof}2029 2030For $r=2$ the inclusions and the conditional expectations are adjoint to each other, and (iii) is the2031statement that for a sequence of embedding--projection pairs the colimit of the embeddings is the limit of2032the projections. The same coincidence, for a different kind of object, is what makes recursive domain2033equations solvable \cite{SP82}. For $r=1$ it fails, and the failure is the Lebesgue decomposition: the2034martingales that do not come from a function on $\FF_\infty$ are the singular measures. The likelihood ratio of a2035biased coin against a fair one is the standard example (\cref{exer:likelihood}).2036 2037\section{The mean ergodic theorem}2038 2039\begin{theorem}[von Neumann]\label{thm:vN}2040\Scl[\cite{vN32}] Let $U$ be an isometry of a Hilbert space and $P$ the orthogonal projection onto the space2041$\Fix(U)$ of invariant vectors. Then $\frac1n\sum_{k=0}^{n-1}U^kv\to Pv$ for every $v$.2042\end{theorem}2043 2044\begin{proof}2045First $\Fix(U)=\Fix(U^*)$: if $Uv=v$ then2046$\|U^*v-v\|^2=\|U^*v\|^2-2\operatorname{Re}\langle v,Uv\rangle+\|v\|^2\le0$, and symmetrically. Hence the orthogonal complement of2047$\Fix(U)$ is the closure of the range of $1-U$. On $\Fix(U)$ the averages are constant. On a vector2048$w-Uw$ they equal $(w-U^nw)/n$, which tends to zero. The averages are contractions, so the convergence2049extends 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