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 1829–1928 of 4249. Source text is displayed literally.
1829\end{example}1830 1831The example shows what McMillan's theorem must assume. For a non-ergodic source the quantity1832$-\frac1n\log\mu_n(x_1\dots x_n)$ still converges, but to a random variable, the entropy of the ergodic component1833that produced $x$.1834 1835\section*{Notes}1836 1837For ergodic theory see \cite{Wal82,Pet83}; for its use in information theory, \cite{Gra09,Gra11,Bil65}.1838Khinchin's treatment is \cite[\S4]{Khi56}. The categorical ergodic decomposition is due to Moss and Perrone1839\cite{MP23}, with further development by Ensarguet and Perrone \cite{EP23}; the synthetic zero--one laws1840of \cite{FR20} give another route to \cref{prop:iid}. Affinity of the entropy rate and its integral1841representation are due to Jacobs \cite{Jac59}; the corresponding statements for the rate of transmission1842are due to Parthasarathy \cite{Par61} and Breiman \cite{Bre60}.1843 1844\section*{Exercises}1845 1846\begin{exercise}1847Let $Q$ be a stochastic matrix with exactly two closed irreducible classes and no transient states. Show1848that the stationary Markov sources with matrix $Q$ form a segment, that its endpoints are ergodic, and that1849the entropy is an affine function on it.1850\end{exercise}1851 1852\begin{exercise}\label{exer:cylinders}1853Show that a stationary source is ergodic iff for all cylinders $C,C'$,1854$\frac1n\sum_{k=0}^{n-1}\mu(C\cap T^{-k}C')\to\mu(C)\mu(C')$.1855\end{exercise}1856 1857\begin{exercise}1858Prove the two inequalities for $H_n(\mu)$ in the proof of \cref{thm:affine}, and show by an example that1859the upper one can be an equality for every $n$.1860\end{exercise}1861 1862\begin{exercise}\label{exer:mixlimit}1863For the source of \cref{ex:mixture} show that $-\frac1n\log\mu_n(x_1\dots x_n)$ converges almost surely to a random1864variable taking the values $\hb(0.1)$ and $1$ with probability $\tfrac12$ each.1865\end{exercise}1866 1867\begin{exercise}1868Let $\mu$ give probability $\tfrac12$ to each of the two sequences of alternating bits. Show that $\mu$ is1869ergodic for $T$ and not for $T^2$, and that its entropy is zero.1870\end{exercise}1871%% ---- end ch/06-ergodic.tex ----1872%% ---- begin ch/07-martingales.tex ----1873\chapter{Martingales}\label{ch:martingales}1874 1875To prove McMillan's theorem Khinchin needs to know that the conditional probability of the next letter given1876the last $n$ letters converges as $n\to\infty$. He obtains this from Doob's martingale convergence theorem,1877to which he devotes a section. This chapter looks at the same convergence from the side of the category of1878probability spaces. Conditioning on a $\sigma$-algebra is an idempotent morphism, a filtration is an1879increasing sequence of idempotents, and the convergence of a martingale in mean is the convergence of that1880sequence to its supremum. The same picture contains the mean ergodic theorem. What it does not contain is1881almost sure convergence, and we say so.1882 1883\section{The setting}1884 1885Let $(X,\FF,p)$ be a probability space. A \term{filtration} is an increasing sequence of sub-$\sigma$-algebras1886$\FF_1\subseteq\FF_2\subseteq\cdots$, and $\FF_\infty$ is the $\sigma$-algebra they generate. A \term{martingale} is a1887sequence of integrable functions $M_n$, with $M_n$ measurable for $\FF_n$ and $\E[M_{n+1}\st\FF_n]=M_n$. It is1888\term{closed} if $M_n=\E[f\st\FF_n]$ for a single integrable $f$.1889 1890For a stationary source and a letter $a$, let $\FF_n$ be generated by $x_{-n},\dots,x_{-1}$. Then1891\[ M^a_n(x)=\mu(x_0=a\st x_{-n},\dots,x_{-1})=\E\bigl[1_{\{x_0=a\}}\st\FF_n\bigr] \]1892is a closed martingale with values in $[0,1]$. This is the object Khinchin studies.1893 1894\section{Probability spaces and kernels}1895 1896\begin{definition}\label{def:krn}1897$\Krn$ is the category whose objects are standard Borel probability spaces $(X,p)$ and whose morphisms1898$(X,p)\to(Y,q)$ are Markov kernels $k$ with $k\circ p=q$, two kernels being identified when they agree1899$p$-almost surely.1900\end{definition}1901 1902A morphism of $\Krn$ is the same as a \term{coupling} of $p$ and $q$, the joint law $p\rtimes k$ on $X\times Y$.1903Reading the coupling from the other side gives the Bayesian inverse $k^\dagger\colon(Y,q)\to(X,p)$.1904 1905\begin{proposition}\label{prop:dagger}1906\Sli[\cite{CJ19,Fri20,DDGK16}] Bayesian inversion makes $\Krn$ a dagger category:1907$k^{\dagger\dagger}=k$, $(l\circ k)^\dagger=k^\dagger\circ l^\dagger$, $\id^\dagger=\id$. For each $r\in[1,\infty]$ there is a1908functor $L^r\colon\Krn^{\op}\to\Ban$ to Banach spaces and contractions, sending $(X,p)$ to $L^r(p)$ and $k$ to1909$(k^*g)(x)=\int g(y)\,k(dy\st x)$. For $r=2$ it lands in Hilbert spaces and preserves daggers:1910$(k^\dagger)^*=(k^*)^\dagger$.1911\end{proposition}1912 1913A measure-preserving map $f\colon(X,p)\to(Y,q)$ is a morphism of $\Krn$, and $f^*g=g\circ f$ is an isometric1914embedding. Since $f$ is deterministic, $f\circ f^\dagger=\id_Y$. The other composite1915\[ e_f=f^\dagger\circ f\colon(X,p)\to(X,p) \]1916is therefore idempotent and self-adjoint, $e_f\circ e_f=e_f=e_f^\dagger$. As a kernel it does this: given $x$,1917forget everything except $f(x)$, and draw a new point from the conditional distribution given $f(x)$.1918 1919\begin{proposition}[Conditional expectations are idempotents]\label{prop:idem}1920\Sli[\cite{PVB24}]1921\begin{enumerate}[label=(\roman*)]1922\item Every sub-$\sigma$-algebra $\GG\subseteq\FF$ arises, up to null sets, from a measure-preserving map1923$f$, and so defines a dagger idempotent $e_\GG=e_f$ on $(X,p)$ that splits through a deterministic map.1924\item $L^r$ sends $e_\GG$ to the conditional expectation $\E[\,\cdot\st\GG]$; for $r=2$ this is the orthogonal1925projection onto $L^2(\GG)$.1926\item $\GG\subseteq\GG'$ iff $e_\GG\circ e_{\GG'}=e_\GG$, and then also $e_{\GG'}\circ e_\GG=e_\GG$.1927\end{enumerate}1928\end{proposition}