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 2381–2480 of 4249. Source text is displayed literally.
2381\end{definition}2382 2383A \term{memoryless} channel is given by a stochastic matrix $W\colon A\to B$ and2384$\nu_x=\bigotimes_nW(\,\cdot\st x_n)$: the output letters are independent given the input, and the $n$-th2385depends on $x_n$ alone. It has all three properties with $m=0$.2386 2387\section{Connecting a channel to a source}2388 2389By \cref{prop:dyn}, a stationary channel is a morphism $(\AZ,T)\to(\BZ,T)$ of $\Dyn$ and a stationary source is a2390state.2391 2392\begin{definition}2393The \term{compound source} of a source $[A,\mu]$ and a channel $[A,\nu,B]$ is the state2394\[ \omega=(\id\otimes\nu)\circ\cpy\circ\mu\quad\text{on }\AZ\times\BZ=(A\times B)^{\Z}, \]2395that is, $\omega(M\times N)=\int_M\nu_x(N)\,d\mu(x)$. Its second marginal $\eta=\nu\circ\mu$ is the \term{output source}.2396\end{definition}2397 2398\begin{figure}[ht]\centering2399\begin{tikzpicture}[x=1cm,y=1cm]2400 \node[ogbox] (mu) at (0,0) {$\mu$};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 invariant