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 1581–1680 of 4249. Source text is displayed literally.
1581$H_n\le H(s_0)+H(x_0\dots x_{n-1}\st s_0)$. Divide by $n$.1582\end{proof}1583 1584A general coalgebra can be made unifilar at the cost of enlarging the state space. Replace the state by the1585\term{belief}, the conditional distribution $b\in\Delta(S)$ of the current state given the letters emitted1586so far. The belief emits a letter with distribution $e_b=\sum_sb(s)\,c(\,\cdot\,,S\st s)$ and is then updated1587by Bayes' rule to a new belief $\tau(b,a)$ that is a function of $b$ and the letter. This is the1588determinization of the coalgebra in the sense of the generalized powerset construction \cite{SBBR13},1589carried out for the distribution monad instead of the powerset.1590 1591\begin{theorem}[Blackwell]\label{thm:blackwell}1592\Srf[\cite{Bla57}] Let $\beta$ be a stationary distribution of the belief process on $\Delta(S)$ arising from1593the invariant initial distribution $\sigma$. Then1594\[ H(\mu)=\int_{\Delta(S)}H(e_b)\,d\beta(b), \]1595which is the formula of \cref{prop:unifilar} for the determinized coalgebra. For every $n\ge1$,1596\[ H(x_n\st x_0,\dots,x_{n-1},s_0)\ \le\ H(\mu)\ \le\ H(x_n\st x_0,\dots,x_{n-1}), \]1597and both bounds converge to $H(\mu)$.1598\end{theorem}1599 1600The measure $\beta$ can be singular and is not computable in closed form in general; that is the sense in1601which the entropy of a hidden Markov source has no formula. The bounds are effective.1602 1603\begin{example}\label{ex:hmm}1604Let the state follow the chain of \cref{ex:markov} and let the emitted letter be the state passed through a1605binary symmetric channel with flip probability $0.2$. The lower and upper bounds of \cref{thm:blackwell} are1606$0.9033$ and $0.9055$ at $n=4$ and agree to four places, at $0.9052$, from $n=8$ on. Hiding the state behind1607noise has raised the entropy from $0.572$ to $0.905$ bits per letter.1608\end{example}1609 1610\section{Entropy as an invariant}1611 1612Let $\phi\colon(\AZ,\mu)\to(\BZ,\eta)$ be a stationary code with $\phi\circ\mu=\eta$; one says that $\eta$ is a1613\term{factor} of $\mu$.1614 1615\begin{theorem}[Kolmogorov--Sinai]\label{thm:KS}1616\Scl[\cite{Kol58,Sin59}] If $\eta$ is a factor of $\mu$ then $H(\eta)\le H(\mu)$. In particular isomorphic1617stationary sources have the same entropy.1618\end{theorem}1619 1620\begin{proof}[Proof for sliding block codes]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, as