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 1789–1888 of 4249. Source text is displayed literally.
1789\Scl[\cite{Jac59,Par61}] The function $H\colon M_T(A)\to[0,\log|A|]$ is affine and upper semicontinuous, and1790\[ H(\mu)=\int H(\mu_e)\,d\lambda(e) \]1791for the ergodic decomposition of $\mu$.1792\end{theorem}1793 1794\begin{proof}1795Let $\mu=\lambda\mu'+(1-\lambda)\mu''$. The block law $\mu_n$ is the same mixture of $\mu'_n$ and $\mu''_n$, and by1796concavity of $H$ and \cref{prop:convexlinear},1797\[ \lambda H_n(\mu')+(1-\lambda)H_n(\mu'')\ \le\ H_n(\mu)\ \le\ \lambda H_n(\mu')+(1-\lambda)H_n(\mu'')+\hb(\lambda). \]1798Divide by $n$ and let $n\to\infty$. For semicontinuity, $H=\inf_nH_n/n$ by \cref{prop:rate}, and each $H_n$ is1799continuous, depending on finitely many cylinder probabilities. An affine upper semicontinuous function on a1800Choquet simplex satisfies the barycentric formula.1801\end{proof}1802 1803The term $\hb(\lambda)$ is the entropy of the choice between the two components. It is paid once, and its1804contribution per letter vanishes. This is the first instance of something that recurs: passing to rates1805turns a concave function into an affine one, and more generally removes whatever is not extensive.1806 1807\begin{corollary}\label{cor:sup}1808\Scl For an affine upper semicontinuous function on $M_T(A)$, the supremum over all stationary sources is1809attained 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$.