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 1641–1740 of 4249. Source text is displayed literally.
1641diagrams in a Markov category are in \cite[\S7]{Fri20}. For the classical theory of sources see1642\cite{Gra11,Bil65}. The Curtis--Hedlund--Lyndon theorem is \cite{Hed69}; see \cite{LM95}. Coalgebraic trace1643semantics for probabilistic systems was developed in \cite{HJS07,KK13}, and determinization in \cite{SBBR13}.1644Blackwell's theorem is \cite{Bla57}; the bounds are in \cite[\S4.5]{CT06}.1645 1646\section*{Exercises}1647 1648\begin{exercise}1649For the Markov source with $q_{01}=a$ and $q_{10}=b$, show that $H(\mu)=\frac{b\,\hb(a)+a\,\hb(b)}{a+b}$, and find the1650maximum over $a,b$. When is $H(\mu)$ equal to the entropy of the one-letter marginal?1651\end{exercise}1652 1653\begin{exercise}1654Let $\mu$ be a stationary source on $\{0,1\}$ and let $\phi$ be the sliding block code1655$\phi(x)_n=x_n+x_{n+1}\bmod2$. Show that $H(\phi\circ\mu)\le H(\mu)$ directly, and that equality holds when1656$\mu$ is the source of independent fair bits. Is $\phi$ an isomorphism in that case?1657\end{exercise}1658 1659\begin{exercise}\label{exer:cofreefinite}1660Let $N\ge1$ and let $\Z/N$ act on $B^{\Z/N}$ by rotation. Show that for every $\Z/N$-set $X$, equivariant maps1661$X\to B^{\Z/N}$ correspond to maps $X\to B$, and count the equivariant maps $A^{\Z/N}\to B^{\Z/N}$.1662\end{exercise}1663 1664\begin{exercise}1665Let $c\colon S\to A\times S$ be a coalgebra in which the next state is a function $s'=\tau(a)$ of the emitted1666letter alone. Show that it generates a Markov source on $A$, find the transition matrix, and compute the1667entropy. Show that every stationary Markov source arises in this way with $S=A$.1668\end{exercise}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