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 1621–1720 of 4249. Source text is displayed literally.
1621If $\phi$ has window radius $r$, a block of $n$ output letters is a function of a block of $n+2r$ input1622letters, so $H_n(\eta)\le H_{n+2r}(\mu)$ by \cref{thm:functor}. Divide by $n$. The general case follows by1623approximating a measurable $\phi_0$ by functions of finitely many coordinates.1624\end{proof}1625 1626So the entropy rate is a functor from stationary sources and stationary codes to the poset1627$([0,\infty),\ge)$. It is the infinite-time counterpart of \cref{thm:functor}, with one difference: for1628finite schemes the functor recorded the amount lost, a number attached to each morphism, and here only1629the inequality survives. It does not extend to a monotone function along stochastic morphisms. A noisy1630channel can raise the entropy of what passes through it, as \cref{ex:hmm} shows. The quantity that behaves1631well for all morphisms of $\Dyn$ is the information rate of \cref{ch:channels}.1632 1633Kolmogorov introduced \cref{thm:KS} into ergodic theory in 1958, taking the definition from Shannon, in1634order to show that the independent sources with distributions $(\tfrac12,\tfrac12)$ and1635$(\tfrac13,\tfrac13,\tfrac13)$ are not isomorphic. Khinchin's papers, which appeared in the years just before,1636were among the routes by which Shannon's ideas reached Soviet probabilists.1637 1638\section*{Notes}1639 1640The categorical treatment of infinite products is due to Fritz and Rischel \cite{FR20}; categories of1641diagrams 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}.