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

1569The entropy of such a source is not given by a formula in terms of $c$ and $\sigma$ in general, but there1570is a case where it is. Call $c$ \term{unifilar} if the next state is a function of the current state and1571the emitted letter, $c(a,s'\st s)=e_s(a)\,[s'=\tau(s,a)]$.1572 1573\begin{proposition}\label{prop:unifilar}1574\Scl[\cite{Sha48}] For a unifilar coalgebra with invariant state distribution $\sigma$,1575$H(\mu)=\sum_s\sigma(s)\,H(e_s)$.1576\end{proposition}1577 1578\begin{proof}1579Let $s_0$ be the initial state. Given $s_0$ and $x_0,\dots,x_{n-1}$ the state $s_n$ is determined, so1580$H(x_n\st x_0,\dots,x_{n-1},s_0)=\sum_s\sigma(s)H(e_s)$ for every $n$. Hence $H_n\ge H(x_0\dots x_{n-1}\st s_0)=n\sum_s\sigma(s)H(e_s)$ and1581$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}