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 1809–1908 of 4249. Source text is displayed literally.
1809attained and equals the supremum over ergodic sources.1810\end{corollary}1811 1812Khinchin defines the capacity of a channel as a supremum over ergodic sources and calls it the ergodic1813capacity, leaving open whether a supremum over all stationary sources would be larger. The corollary1814reduces that question to showing that the rate of transmission is affine and upper semicontinuous in the1815source (\cref{ch:channels}).1816 1817\section{An example}1818 1819\begin{example}\label{ex:mixture}1820Let $\mu$ be the equal mixture of two sources of independent bits, one with $\Prob(1)=0.1$ and one with1821$\Prob(1)=0.5$. It is stationary and not ergodic: the limiting frequency of ones is an invariant function1822taking two values. By \cref{thm:affine},1823\[ H(\mu)=\tfrac12\bigl(\hb(0.1)+1\bigr)\approx0.7345. \]1824The normalized block entropies $H_n/n$ are $0.8106$, $0.7445$, $0.7355$ for $n=10,100,1000$; the excess over1825the limit is at most $1/n$. But a typical long block does not have probability near $2^{-0.7345\,n}$. With1826probability $\tfrac12$ it comes from the first component and has probability near $2^{-0.469\,n}$, and with1827probability $\tfrac12$ it comes from the second and has probability near $2^{-n}$. The entropy is the average1828of two rates, and no long block exhibits it.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$ to