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

1669 1670\begin{exercise}1671Prove the upper and lower bounds of \cref{thm:blackwell}, and show that the lower bound is nondecreasing and1672the upper bound nonincreasing in $n$.1673\end{exercise}1674%% ---- end ch/05-sources.tex ----1675%% ---- begin ch/06-ergodic.tex ----1676\chapter{Ergodic Sources}\label{ch:ergodic}1677 1678The coding theorems are about what happens along a single long sequence, and a statement about one1679sequence can reflect the source only if the source does not secretly consist of several. Ergodicity is the1680hypothesis that it does not. This chapter states it in three equivalent ways: by invariant sets, as1681Khinchin does; as extremality in the convex set of stationary sources; and as determinism on the invariant1682$\sigma$-algebra, in the formulation of Moss and Perrone. It then shows that the entropy of a source is an1683affine function, which is why the ergodic case is the only one that needs to be treated.1684 1685\section{Invariant sets}1686 1687Let $[A,\mu]$ be a stationary source. A set $S\in\FF_A$ is \term{invariant} if $T^{-1}S=S$. The invariant sets1688form a $\sigma$-algebra $\II$. A measurable function is $\II$-measurable iff it is invariant,1689$f\circ T=f$.1690 1691\begin{definition}1692A stationary source is \term{ergodic} if every invariant set has measure $0$ or $1$; equivalently, if every1693invariant function is almost surely constant.1694\end{definition}1695 1696\begin{proposition}\label{prop:iid}1697\Scl The source $p^{\otimes\Z}$ of independent letters is ergodic. A stationary Markov source with irreducible1698transition matrix is ergodic.1699\end{proposition}1700 1701\begin{proof}1702Let $S$ be invariant and $\varepsilon>0$. Choose a set $C$ depending on the coordinates in $[-m,m]$ with1703$\mu(S\triangle C)<\varepsilon$. For $n>2m$ the set $T^{-n}C$ depends on a disjoint window, so for independent1704letters $\mu(C\cap T^{-n}C)=\mu(C)^2$. Since $S=S\cap T^{-n}S$, we get $|\mu(S)-\mu(S)^2|<4\varepsilon$, and1705$\mu(S)\in\{0,1\}$. For a Markov source the same argument works with $\mu(C\cap T^{-n}C)$ replaced by its1706Ces\`aro averages, which converge to $\mu(C)^2$ when the matrix is irreducible.1707\end{proof}1708 1709A mixture $\lambda\mu'+(1-\lambda)\mu''$ of two different stationary sources, $0<\lambda<1$, is stationary and1710never ergodic (\cref{cor:extreme}).1711 1712\begin{theorem}[Birkhoff]\label{thm:birkhoff}1713\Scl[\cite{Bir31}] Let $\mu$ be stationary and $f\in L^1(\mu)$. The averages1714$A_nf=\frac1n\sum_{k=0}^{n-1}f\circ T^k$ converge almost surely and in $L^1$ to the conditional expectation1715$\E[f\st\II]$. If $\mu$ is ergodic the limit is the constant $\int f\,d\mu$.1716\end{theorem}1717 1718Khinchin quotes this theorem and uses the almost sure statement. For McMillan's theorem in the form he1719proves, convergence in $L^1$ is enough, and that part has a short proof by Hilbert space geometry which we1720give in \cref{ch:martingales}.1721 1722\section{The simplex of stationary sources}1723 1724Let $M_T(A)$ be the set of stationary sources with alphabet $A$, with the topology of convergence of the1725probabilities of cylinders.1726 1727\begin{theorem}[Ergodic decomposition]\label{thm:decomposition}1728\Scl $M_T(A)$ is a compact convex metrizable set, and a Choquet simplex. Its extreme points are the ergodic1729sources. 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}