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 1429–1528 of 4249. Source text is displayed literally.
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$ is1481a sum of a nonincreasing nonnegative sequence, so $H_n/n$ converges to $\lim c_k$; the infimum is Fekete's1482lemma for the subadditive sequence $H_n$.1483\end{proof}1484 1485\begin{definition}1486The common value $H(\mu)$ of the limits in \cref{prop:rate} is the \term{entropy} of the source, in bits per1487letter. It satisfies $0\le H(\mu)\le\log|A|$.1488\end{definition}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}