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

1769The proof of \textup{(iii)} is a short string-diagram argument that uses no limiting procedure and does not1770depend on the cardinality of $G$.1771\end{theorem}1772 1773Part (ii) is the classical definition read in $\Stoch$, where the deterministic states are exactly the1774$\{0,1\}$-valued measures. Part (iii) recovers \cref{thm:decomposition} for standard Borel $X$. What the1775formulation adds is a statement of where the decomposition comes from. It is the disintegration of $p$ over1776the invariant quotient, and the ergodic components are the fibres. The space $X_{\mathrm{inv}}$ is usually not1777standard Borel, which is one reason to work in $\Stoch$ and not in $\BorelStoch$ here.1778 1779The same quotient organizes the ergodic theorem. On $L^2(\mu)$ the composite of $q$ with its Bayesian1780inverse is the conditional expectation onto invariant functions, and \cref{thm:birkhoff} says that time1781averages converge to it. We return to this in \cref{ch:martingales}.1782 1783\section{Entropy is affine}1784 1785The entropy of a finite scheme is a strictly concave function of the distribution. The entropy of a source1786is not.1787 1788\begin{theorem}\label{thm:affine}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$ is