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

1489 1490For the source that emits independent letters with distribution $p$, the state $p^{\otimes\Z}$, the block1491entropies are $H_n=nH(p)$ and the entropy of the source is $H(p)$. The second expression in (iii) has a1492meaning that the first hides: $H(\mu)$ is the uncertainty of the next letter given the entire past. We make1493this precise in \cref{ch:martingales}.1494 1495\section{Stationary codes and cofreeness}1496 1497A stationary code $\phi\colon\AZ\to\BZ$ is determined by its coordinate at time zero,1498$\phi_0=\pi_0\circ\phi\colon\AZ\to B$, since $\phi(x)_n=\phi_0(T^nx)$. This is a universal property.1499 1500\begin{proposition}\label{prop:cofree}1501\Srf[\cite{Hed69}] In the category of sets, of measurable spaces, or of compact Hausdorff spaces, let $(X,T_X)$ be1502an object with an automorphism. Then composition with $\pi_0$ is a bijection between equivariant maps1503$(X,T_X)\to(\BZ,T)$ and maps $X\to B$. That is, $(\BZ,T)$ is the cofree system on $B$. Consequently:1504\begin{enumerate}[label=(\roman*)]1505\item stationary codes $\AZ\to\BZ$ correspond to measurable functions $\AZ\to B$;1506\item continuous equivariant maps $\AZ\to\BZ$ correspond to continuous functions $\AZ\to B$, which by1507compactness depend on finitely many coordinates: they are the \term{sliding block codes}1508$\phi(x)_n=\Phi(x_{n-r},\dots,x_{n+r})$ (the Curtis--Hedlund--Lyndon theorem).1509\end{enumerate}1510In $\BorelStoch$ the corresponding statement is false.1511\end{proposition}1512 1513\begin{proof}1514Given $g\colon X\to B$ define $\phi(x)_n=g(T_X^nx)$. This is the unique equivariant map with $\pi_0\circ\phi=g$,1515and it is measurable or continuous when $g$ is, because $\BZ$ is the product in those categories. A1516continuous function from the compact space $\AZ$ to the finite discrete space $B$ is locally constant, and1517finitely many cylinders on which it is constant cover $\AZ$. For the last statement let $X=1$: an1518equivariant kernel $1\to\BZ$ is a stationary source, a kernel $1\to B$ is a distribution on $B$, and many1519stationary sources have the same one-letter marginal.1520\end{proof}1521 1522The failure in the stochastic case is not a technicality. An equivariant kernel $\nu\colon\AZ\to\BZ$1523consists of its time-zero marginal $\AZ\to B$ and, in addition, of the dependence among the output letters1524for a fixed input. The first part is what Khinchin's notion of the memory of a channel controls. The1525second is not controlled by it, and we shall see in \cref{ch:channels} that this is exactly where his1526treatment of ergodicity has a gap.1527 1528\section{Markov chains}1529 1530Let $Q=(q_{ab})$ be a stochastic matrix on $A$ and $\pi$ a stationary distribution, $\pi Q=\pi$. The1531\term{stationary Markov source} has block laws $\mu_n(x_1\dots x_n)=\pi(x_1)\,q_{x_1x_2}\cdots q_{x_{n-1}x_n}$.1532 1533\begin{proposition}\label{prop:markov}1534\Scl[\cite{Sha48}; \cite{Khi53}, \S3] The entropy of the stationary Markov source is1535\[ H(\mu)=\sum_a\pi(a)\,H(q_{a\,\cdot})=-\sum_{a,b}\pi(a)\,q_{ab}\log q_{ab}. \]1536\end{proposition}1537 1538\begin{proof}1539By the Markov property $c_n=H(x_0\st x_{-1})$ for all $n\ge1$.1540\end{proof}1541 1542\begin{example}\label{ex:markov}1543Let $A=\{0,1\}$ with $q_{01}=0.1$ and $q_{10}=0.3$. Then $\pi=(0.75,0.25)$ and1544$H(\mu)=0.75\,\hb(0.1)+0.25\,\hb(0.3)\approx0.572$ bits per letter. A source emitting independent letters with the1545same marginal has entropy $\hb(0.25)\approx0.811$. The difference is what the memory of the chain is worth to1546someone predicting it.1547\end{example}1548 1549\section{Finite-state sources as coalgebras}1550 1551A Markov chain is the simplest machine that emits a sequence. The general finite machine has a finite set1552$S$ of internal states and, at each step, emits a letter and moves to a new state, the pair being drawn1553from a distribution that depends on the current state. That is a morphism1554\[ c\colon S\longrightarrow A\times S\quad\text{in }\FinStoch, \]1555a coalgebra for the functor $A\times-$. With an initial distribution on $S$ it generates a process, called1556a hidden Markov source or a function of a Markov chain.1557 1558\begin{theorem}\label{thm:trace}1559\Sli[\cite{KK13}; cf.\ \cite{HJS07}] In $\BorelStoch$ the space $A^{\N}$ of one-sided sequences, with the1560isomorphism $A^{\N}\iso A\times A^{\N}$ splitting off the first letter, is the final coalgebra of the functor1561$A\times-$. For a coalgebra $c\colon S\to A\times S$ the unique coalgebra morphism $S\to A^{\N}$ assigns to1562each state the law of the sequence emitted from it.1563\end{theorem}1564 1565Uniqueness is the extension theorem again: a coalgebra morphism is determined on cylinders by induction on1566their length. If the initial distribution $\sigma$ is invariant for the state process, the emitted1567one-sided process is stationary and extends uniquely to a stationary source on $\AZ$.1568 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},