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 2429–2528 of 4249. Source text is displayed literally.
2429\end{theorem}2430 2431\begin{proof}2432$\cpy$ and $\nu$ are morphisms of $\Dyn$ and $\mu$ is a state, so $\omega$ is a state of $\Dyn$. Written out2433(\cref{fig:hookup}),2434\begin{align*}2435 (T\otimes T)\circ(\id\otimes\nu)\circ\cpy\circ\mu&=(\id\otimes\nu)\circ(T\otimes T)\circ\cpy\circ\mu\\2436 &=(\id\otimes\nu)\circ\cpy\circ T\circ\mu=\omega,2437\end{align*}2438using in turn the equivariance of $\nu$, the determinism of $T$, and the invariance of $\mu$.2439\end{proof}2440 2441The same reasoning shows that channels compose: from $[A,\nu,B]$ and $[B,\nu',C]$ one gets $[A,\nu'\circ\nu,C]$,2442stationary if both are. A stationary code is a deterministic channel, and coding a source before sending it2443through a channel is composition. Khinchin uses all of this in his last chapter, where a code is treated2444as a channel so that the previous theorems apply to it.2445 2446\section{Anticipation and naturality}2447 2448To see what absence of anticipation means, take one-sided time. The space $A^{\N}$ of sequences2449$x_1x_2\dots$ is the limit of the tower $\cdots\to A^{n+1}\to A^n\to\cdots$ of maps forgetting the last letter.2450 2451\begin{proposition}\label{prop:natural}2452\Srf A kernel $\nu\colon A^{\N}\to B^{\N}$ is without anticipation iff it is induced by a family of kernels2453$\nu_n\colon A^n\to B^n$ in $\FinStoch$ that commutes with the maps of the two towers, a natural2454transformation. The correspondence is bijective. A memoryless channel is the family $\nu_n=W^{\otimes n}$.2455\end{proposition}2456 2457\begin{proof}2458If $\nu$ is without anticipation, the law of $y_1\dots y_n$ is a function of $x_1\dots x_n$, which defines2459$\nu_n$, and marginalizing $y_{n+1}$ gives naturality. Conversely a natural family composed with the2460projections $A^{\N}\to A^n$ is a compatible family of kernels $A^{\N}\to B^n$, which by \cref{thm:kolmogorov} is a2461kernel into $B^{\N}$.2462\end{proof}2463 2464Natural transformations between towers of sets are the causal functions on streams, and they are the2465morphisms between stream objects in the topos of trees, the presheaf category on the ordinal $\omega$2466\cite{BMSS12}. The proposition is the stochastic version: channels without anticipation are natural2467transformations of towers in $\FinStoch$. Among them the memoryless ones are those that are also2468compatible with concatenation, $\nu_{m+n}=\nu_m\otimes\nu_n$. Memory of length $m$ lies in between.2469 2470\section{Ergodicity: a gap and its repair}2471 2472Khinchin's second theorem about the compound source reads: if the source is ergodic and the channel is2473stationary, without anticipation and of finite memory, then the compound source is ergodic. He needs it2474in order to apply McMillan's theorem to the compound source.2475 2476\begin{example}\label{ex:gap}2477Let $\nu_x=\tfrac12\delta_{\mathbf0}+\tfrac12\delta_{\mathbf1}$ for every $x$, where $\mathbf0$ and $\mathbf1$ are the constant2478sequences. This channel ignores its input and emits one random bit forever. It is stationary. It is2479without anticipation and has memory $0$ in the sense of \cref{def:channel}, since the law of any output block2480does not depend on $x$ at all. For any source, $\omega=\mu\otimes\nu$, and the set $\AZ\times\{\mathbf0\}$ is invariant2481with probability $\tfrac12$. The compound source is not ergodic.2482\end{example}2483 2484So the theorem fails under the stated hypotheses. Breiman noted that Khinchin's definition of finite memory2485is not restrictive enough for his results, and Takano and Feinstein had by then added the missing2486condition \cite{Bre60,Tak58,Fei59}.2487 2488\begin{definition}2489A channel has \term{finite output memory} $m$ if, for every $x$, the blocks $(y_s,\dots,y_t)$ and2490$(y_{s'},\dots,y_{t'})$ are independent under $\nu_x$ whenever $s'-t>m$.2491\end{definition}2492 2493\begin{theorem}\label{thm:ergodicchannel}2494\Scl[\cite{Tak58,Fei59,Adl61}] Let the channel be stationary, of finite memory in the sense of2495\cref{def:channel} and of finite output memory. If the source is ergodic, the compound source and the output2496source are ergodic.2497\end{theorem}2498 2499\begin{proof}2500Let $E=C\times D$ and $E'=C'\times D'$ be products of cylinders in $\AZ$ and $\BZ$. By finite memory2501$f(x)=1_C(x)\,\nu_x(D)$ depends on finitely many coordinates of $x$, and likewise $f'$. For large $k$ the output2502blocks defining $D$ and $T^{-k}D'$ are more than $m$ apart, so by finite output memory and stationarity2503\[ \omega(E\cap T^{-k}E')=\int f(x)\,f'(T^kx)\,d\mu(x). \]2504By the mean ergodic theorem the Ces\`aro averages of the right side converge to $\int f\,d\mu\int f'\,d\mu=\omega(E)\,\omega(E')$,2505and this criterion on cylinders is equivalent to ergodicity (\cref{exer:cylinders}).2506\end{proof}2507 2508The categorical picture explains the shape of the gap. By \cref{prop:cofree}, an equivariant map into $\BZ$ is2509determined by its time-zero coordinate, but an equivariant kernel is not. A stationary channel consists of2510the conditional laws of finite output blocks given the input, and of the way these fit together across2511time. Khinchin's memory condition bounds the first, the dependence on the input. Ergodicity of the2512composite is a statement about the second, and \cref{ex:gap} is a channel that is as trivial as possible in2513the first respect and as bad as possible in the second. In $\Dyn$ the ergodic states are not preserved by2514arbitrary morphisms; \cref{thm:ergodicchannel} describes a class of morphisms that do preserve them.2515Deterministic morphisms always do, since a factor of an ergodic source is ergodic.2516 2517\section{Rate and capacity}2518 2519\begin{definition}[\cite{Khi56}, \S10]2520For a stationary source and channel, the \term{rate of transmission} is2521\[ R(\mu,\nu)=H(\mu)+H(\eta)-H(\omega)=\lim_{n\to\infty}\frac1n\,I(x_1\dots x_n;\,y_1\dots y_n). \]2522The \term{ergodic capacity} $C$ of the channel is the supremum of $R(\mu,\nu)$ over ergodic sources $\mu$.2523\end{definition}2524 2525Since $\mu\mapsto\eta$ and $\mu\mapsto\omega$ are affine, \cref{thm:affine} gives at once:2526 2527\begin{proposition}\label{prop:rateaffine}2528\Scl[\cite{Par61}] For every stationary channel, $R(\,\cdot\,,\nu)$ is an affine function on the simplex of