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 1381–1480 of 4249. Source text is displayed literally.
1381\end{exercise}1382 1383\begin{exercise}1384Prove \cref{prop:chainD}, and show that equality holds in \cref{thm:DPI} iff the two Bayesian inverses agree:1385$r(\,\cdot\st y)=r'(\,\cdot\st y)$ for all $y$ in the support of $f\circ p$.1386\end{exercise}1387 1388\begin{exercise}1389Compute $\TV(\cpy\circ p,\,p\otimes p)$ and $\KL{\cpy\circ p}{p\otimes p}$ for $p=(\tfrac12,\tfrac14,\tfrac14)$.1390For which states on $n$ points is each largest?1391\end{exercise}1392 1393\begin{exercise}\label{exer:meet}1394Let $X,Y$ be bits with joint distribution $r(0,0)=r(1,1)=0.4$, $r(0,1)=r(1,0)=0.1$. Compute $I(X;Y)$ and show1395that $X\wedge Y$ is trivial. Then give an example in which $I(X;Y)=H[X\wedge Y]>0$.1396\end{exercise}1397 1398\begin{exercise}1399Let $X$ be uniform on $n$ points and let $Y=X$ with probability $1-\varepsilon$, and otherwise uniform on the1400other $n-1$ points, with $\varepsilon<1-\tfrac1n$. Show that equality holds in Fano's inequality.1401\end{exercise}1402%% ---- end ch/04-inequalities.tex ----1403\part{Sources}1404%% ---- begin ch/05-sources.tex ----1405\chapter{Sources}\label{ch:sources}1406 1407A source, for Khinchin, is a probability measure $\mu$ on the space $\AZ$ of doubly infinite sequences of1408letters from a finite alphabet $A$; it is stationary when $\mu$ is invariant under the shift. This chapter1409sets up the same objects in a Markov category. The sequence space is an infinite tensor product, a source is1410a state on it, and stationary sources and the maps between them are the states and morphisms of a category1411of dynamical systems. We then define the entropy rate, compute it for Markov chains as Khinchin does in his1412first paper, and read finite-state sources as coalgebras.1413 1414\section{Sequence spaces}1415 1416Let $\BorelStoch$ be the category of standard Borel spaces and Markov kernels; it is a Markov category1417containing $\FinStoch$, and its deterministic morphisms are the measurable maps (\cref{app:toolkit}). For a1418finite alphabet $A$ the space $\AZ$ carries the product $\sigma$-algebra $\FF_A$, generated by the1419\term{cylinders}, the sets of sequences with prescribed letters at finitely many places. For a finite set1420$F\subset\Z$ let $\pi_F\colon\AZ\to A^F$ be the projection.1421 1422\begin{theorem}[Kolmogorov extension]\label{thm:kolmogorov}1423\Sli[\cite{FR20}] In $\BorelStoch$ the object $\AZ$, with the projections $\pi_F$, is the limit of the diagram1424of finite powers $A^F$ and marginalization maps, and this limit is preserved by tensoring with any object.1425Explicitly, for every $Y$ the kernels $Y\to\AZ$ correspond bijectively to families of kernels1426$k_F\colon Y\to A^F$ that are compatible with marginalization.1427\end{theorem}1428 1429Such a limit is called a \term{Kolmogorov product}, and $\AZ=\bigotimes_{n\in\Z}A$ is the infinite tensor1430power of $A$. For $Y=1$ the theorem is the classical statement that a measure on $\AZ$ is the same as a1431consistent family of finite-dimensional distributions. The Kolmogorov product is a categorical product only1432in the subcategory of deterministic morphisms. A kernel into $\AZ$ is not determined by its components into1433the single factors $A$, and this failure will matter below.1434 1435\section{Stationary sources}1436 1437The \term{shift} $T\colon\AZ\to\AZ$, $(Tx)_n=x_{n+1}$, is a deterministic isomorphism. A \term{source} $[A,\mu]$1438is a state $\mu\colon1\to\AZ$; it is \term{stationary} if $T\circ\mu=\mu$. By \cref{thm:kolmogorov} a stationary1439source is the same as a sequence of distributions $\mu_n$ on $A^n$, $n\ge1$, the laws of the blocks1440$x_1\dots x_n$, such that both the first $n$ and the last $n$ letters of a block distributed by $\mu_{n+1}$1441are distributed by $\mu_n$.1442 1443\begin{definition}\label{def:dyn}1444$\Dyn$ is the category whose objects are pairs $(X,T_X)$ of a standard Borel space and a measurable1445automorphism, and whose morphisms $(X,T_X)\to(Y,T_Y)$ are the Markov kernels $k\colon X\to Y$ that are1446\term{equivariant}: $k\circ T_X=T_Y\circ k$.1447\end{definition}1448 1449\begin{proposition}\label{prop:dyn}1450\Sli[\cite{Fri20}, \S7] $\Dyn$ is a Markov category, with tensor product, copy and delete maps inherited from1451$\BorelStoch$. Its unit object is the one-point system, and:1452\begin{enumerate}[label=(\roman*)]1453\item a state $1\to(\AZ,T)$ is a stationary source;1454\item a deterministic morphism $(\AZ,T)\to(\BZ,T)$ is a measurable map commuting with the shifts, a1455\term{stationary code};1456\item a general morphism $(\AZ,T)\to(\BZ,T)$ is a stationary channel in the sense of \cref{ch:channels}.1457\end{enumerate}1458\end{proposition}1459 1460The only point to check is that the copy maps are equivariant, and they are because $T$ is deterministic.1461The proposition puts Khinchin's three kinds of object in one place. His remark that a code may be regarded1462as a channel is the inclusion of the deterministic morphisms among all morphisms.1463 1464\section{The entropy rate}1465 1466For a stationary source $\mu$ write $H_n=H(\mu_n)$ for the entropy of a block of length $n$, and $H_0=0$.1467 1468\begin{proposition}\label{prop:rate}1469\Scl[\cite{Sha48,Khi56}] Let $\mu$ be stationary.1470\begin{enumerate}[label=(\roman*)]1471\item $H_{m+n}\le H_m+H_n$.1472\item The increments $c_n=H_{n+1}-H_n=H(x_0\st x_{-n},\dots,x_{-1})$ are nonincreasing in $n$.1473\item The limits $\lim_nH_n/n$ and $\lim_nc_n$ exist and are equal, and equal $\inf_nH_n/n$.1474\end{enumerate}1475\end{proposition}1476 1477\begin{proof}1478(i) is Shannon's inequality for the two halves of a block, whose laws are $\mu_m$ and $\mu_n$ by1479stationarity. (ii) is \cref{lem:SSA}: conditioning on one more letter of the past does not increase the1480entropy; stationarity identifies the conditional entropies with the increments. (iii) $H_n=\sum_{k<n}c_k$ is