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 2401–2500 of 4249. Source text is displayed literally.
2401 \node[dec] (c) at (1.6,0) {};2402 \node[ogbox] (nu) at (3.4,-0.65) {$\nu$};2403 \node[ogbox] (T1) at (5.4,0.65) {$T$};2404 \node[ogbox] (T2) at (5.4,-0.65) {$T$};2405 \draw[fw] (mu) -- (c);2406 \draw[fw] (c) |- (T1);2407 \draw[fw] (c) |- (nu);2408 \draw[fw] (nu) -- (T2);2409 \draw[fw] (T1) -- (7.0,0.65);2410 \draw[fw] (T2) -- (7.0,-0.65);2411 \node at (-1.2,-2.9) {$=$};2412 \node[ogbox] (mu2) at (0,-2.9) {$\mu$};2413 \node[ogbox] (T3) at (1.9,-2.9) {$T$};2414 \node[dec] (c2) at (3.5,-2.9) {};2415 \node[ogbox] (nu2) at (5.4,-3.55) {$\nu$};2416 \draw[fw] (mu2) -- (T3);2417 \draw[fw] (T3) -- (c2);2418 \draw[fw] (c2) |- (7.0,-2.25);2419 \draw[fw] (c2) |- (nu2);2420 \draw[fw] (nu2) -- (7.0,-3.55);2421\end{tikzpicture}2422\caption{The compound source and the proof that it is stationary. The shift slides through $\nu$ by2423equivariance and through the copy node because it is deterministic; it is then absorbed by $\mu$.}\label{fig:hookup}2424\end{figure}2425 2426\begin{theorem}[Khinchin]\label{thm:stationary}2427\Srf[\cite{Khi56}, \S10] If the source and the channel are stationary, so are the compound source and the output2428source.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 memory