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 1729–1828 of 4249. Source text is displayed literally.
1729sources. Every stationary $\mu$ has a unique representation1730\[ \mu=\int\mu_e\,d\lambda(e) \]1731with $\lambda$ a probability measure on the ergodic sources. Concretely, the regular conditional1732probability $\mu_x$ of $\mu$ given $\II$ is an ergodic source for almost every $x$, and1733$\mu=\int\mu_x\,d\mu(x)$.1734\end{theorem}1735 1736\begin{corollary}\label{cor:extreme}1737\Scl Two different ergodic sources are mutually singular, and a proper mixture of two different stationary1738sources is not ergodic.1739\end{corollary}1740 1741\begin{proof}1742If $\mu\ne\mu'$ are ergodic there is a cylinder $C$ with $\mu(C)\ne\mu'(C)$. By \cref{thm:birkhoff} the1743invariant set on which the frequency of visits to $C$ converges to $\mu(C)$ has $\mu$-measure $1$ and1744$\mu'$-measure $0$. Under a proper mixture it has measure strictly between $0$ and $1$.1745\end{proof}1746 1747\section{Ergodicity as determinism}1748 1749The classical definition speaks of sets of measure zero or one. In a Markov category there is a name for a1750state that assigns every event probability zero or one: it is a deterministic state. The catch is that an1751ergodic source is certainly not deterministic as a state on $\AZ$. It is deterministic on a quotient.1752 1753Work in the Markov category $\Stoch$ of all measurable spaces and Markov kernels. Let $G$ be a group or1754monoid acting on an object $X$ by deterministic morphisms; for sources, $G=\Z$ acts by the shift. Call a1755morphism $f\colon X\to Y$ \term{invariant} if $f\circ g=f$ for all $g\in G$. Let $X_{\mathrm{inv}}$ be the set $X$ with1756the $\sigma$-algebra of invariant sets and $q\colon X\to X_{\mathrm{inv}}$ the map that is the identity on points.1757 1758\begin{theorem}[Moss--Perrone]\label{thm:MP}1759\Sli[\cite{MP23}; see also \cite{EP23}]1760\begin{enumerate}[label=(\roman*)]1761\item $q\colon X\to X_{\mathrm{inv}}$ is the universal invariant morphism out of $X$: it is the colimit, in $\Stoch$,1762of the diagram given by the action.1763\item An invariant state $p$ on $X$ is ergodic iff $q\circ p$ is a deterministic state.1764\item In a Markov category with conditionals in which the colimit in \textup{(i)} exists and satisfies a1765compatibility condition, every invariant state $p$ is a mixture of ergodic ones: the conditional1766$k\colon X_{\mathrm{inv}}\to X$ of $p$ given $q$ satisfies $p=k\circ(q\circ p)$, and $k$ is, almost surely with1767respect to $q\circ p$, an ergodic invariant state.1768\end{enumerate}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.