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 2481–2580 of 4249. Source text is displayed literally.
2481with 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 of2529stationary sources.2530\end{proposition}2531 2532\begin{theorem}\label{thm:capacities}2533\Scl[\cite{Bre60,Par61}] For a stationary channel of finite memory and finite output memory,2534$R(\,\cdot\,,\nu)$ is upper semicontinuous. Hence the supremum over all stationary sources equals the ergodic2535capacity, and it is attained by an ergodic source.2536\end{theorem}2537 2538The second statement follows from the first by \cref{cor:sup}. It answers the question Khinchin leaves open2539in his conclusion, where he remarks that capacity is usually defined carelessly and that his own definition2540may give a smaller number than a supremum over all stationary sources. It does not.2541 2542\section{Memoryless channels}2543 2544For a stochastic matrix $W\colon A\to B$ and a distribution $p$ on $A$, write $I(p,W)$ for the mutual2545information of the joint distribution $p\rtimes W$.2546 2547\begin{theorem}\label{thm:dmc}2548\Scl[\cite{Sha48}] The capacity of the memoryless channel with matrix $W$ is2549\[ C(W)=\max_pI(p,W), \]2550attained by the source of independent letters with a maximizing distribution.2551\end{theorem}2552 2553\begin{proof}2554Given the input block, the output letters are independent, so2555$I(x_1^n;y_1^n)=H(y_1^n)-\sum_kH(y_k\st x_k)\le\sum_kI(x_k;y_k)\le n\max_pI(p,W)$. Independent inputs give2556equality.2557\end{proof}2558 2559\begin{example}\label{ex:channels}2560The binary symmetric channel with flip probability $\delta$ has $C=1-\hb(\delta)$; for $\delta=0.1$ this is2561$0.531$. The binary erasure channel, which replaces its input by an erasure symbol with probability $e$,2562has $C=1-e$. The Z-channel, which sends $0$ to $0$ and flips $1$ to $0$ with probability $\delta$, has2563$C=\log\bigl(1+(1-\delta)\,\delta^{\delta/(1-\delta)}\bigr)$, which is $0.763$ for $\delta=0.1$.2564\end{example}2565 2566\section{Capacity as a function on morphisms}2567 2568Restricted to memoryless channels, capacity is a function on the morphisms of $\FinStoch$.2569 2570\begin{proposition}\label{prop:capacity}2571\Scl2572\begin{enumerate}[label=(\roman*)]2573\item $C(\id_X)=\log|X|$, and $C(W)=0$ iff $W$ factors through the one-point set.2574\item $C(V\circ W)\le\min\{C(V),C(W)\}$.2575\item $C(W\otimes W')=C(W)+C(W')$.2576\item If $W$ factors through a set with $r$ elements, then $C(W)\le\log r$.2577\end{enumerate}2578\end{proposition}2579 2580\begin{proof}