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 2969–3068 of 4249. Source text is displayed literally.
2969$[A_0,\mu]$ be an ergodic source with entropy $H_0<C$. For every $\varepsilon>0$ and all large $n$ there are maps2970$A_0^n\to A^{n+m}$ and $B^n\to A_0^n$ such that a block of $n$ letters from the source, encoded, transmitted and2971decoded, is recovered with probability at least $1-\varepsilon$.2972\end{theorem}2973 2974\begin{proof}2975Choose $\delta>0$ with $H_0+\delta<C-\delta$ and put $M=2^{\lceil n(H_0+\delta)\rceil}$. By \cref{prop:corank} the block2976law $\mu_n$ has an $(M,\varepsilon/2)$-compression for large $n$. By \cref{thm:feinsteinmem} the block channel $W_n$2977has a $(2^{\lceil n(C-\delta)\rceil},\varepsilon/2)$-code for large $n$, and $2^{\lceil n(C-\delta)\rceil}\ge M$. Apply2978\cref{lem:compose}.2979\end{proof}2980 2981\section{The second theorem}2982 2983Khinchin's second theorem says that the code can be chosen so that the rate of transmission between the2984source and the received signal is as close as desired to the entropy $H_0$ of the source, or equivalently2985so that the equivocation per letter is small.2986 2987\begin{theorem}[Shannon's second theorem]\label{thm:shannon2}2988\Scl[\cite{Khi56}, \S16] Under the hypotheses of \cref{thm:shannon1}, for every $\varepsilon'>0$ there is a code for2989which the equivocation of the source block given the received block is less than $n\varepsilon'$.2990\end{theorem}2991 2992\begin{proof}2993Take the code of \cref{thm:shannon1}. The received block determines the decoded block, which differs from2994the source block with probability at most $\varepsilon$. By Fano's inequality (\cref{lem:feinstein3})2995the equivocation is at most $1+\varepsilon\,n\log|A_0|$.2996\end{proof}2997 2998In the language of \cref{ch:inequalities}: a morphism within $\varepsilon$ of having a left inverse has2999equivocation at most $\hb(\varepsilon)+\varepsilon\log(\text{size})$. The second theorem is the first theorem passed3000through Fano's inequality, and Khinchin proves it that way.3001 3002\section{The converse, and the two kinds of statement}3003 3004\begin{theorem}[Converse]\label{thm:converse}3005\Scl[\cite{Fan61}] Let $W$ be a memoryless channel with capacity $C$ and $\mu$ a stationary source with entropy3006$H_0>C$. For every $n$ and every pair of maps $A_0^n\to A^n$, $B^n\to A_0^n$ the probability $P_e$ that a block is3007not recovered satisfies3008\[ P_e\ \ge\ \frac{H_0-C-1/n}{\log|A_0|}. \]3009\end{theorem}3010 3011\begin{proof}3012Let $\theta$ be the source block and $\hat\theta$ the decoded block. Then3013$nH_0\le H(\theta)=I(\theta;\hat\theta)+H(\theta\st\hat\theta)\le nC+1+P_e\,n\log|A_0|$, by data processing, \cref{thm:dmc}3014and Fano's inequality.3015\end{proof}3016 3017Compare the ingredients. The converse uses the chain rule, the data-processing inequality, the3018additivity of capacity over independent uses, and Fano's inequality. Each of these is a property of a3019function on morphisms: functoriality, monotonicity under composition, additivity under tensor, continuity3020at identities. The direct theorem uses McMillan's theorem and Feinstein's lemma, which assert that certain3021morphisms exist. The first kind of statement is what category theory handles well, and the converse can be3022stated for any function with those properties.3023 3024\begin{theorem}[A universal property of capacity]\label{thm:universal}3025\Sob Let $\Phi$ assign a number in $[0,\infty)$ to each morphism of $\FinStoch$ so that3026\begin{enumerate}[label=(\roman*)]3027\item $\Phi(g\circ f)\le\min\{\Phi(f),\Phi(g)\}$;3028\item $\Phi(f\otimes g)\le\Phi(f)+\Phi(g)$;3029\item if $f\colon[M]\to[M]$ has all diagonal entries at least $1-\varepsilon$, then3030$\Phi(f)\ge(1-\varepsilon)\log M-1$.3031\end{enumerate}3032Then $\frac1n\log M^*(W^{\otimes n},\varepsilon)\le(\Phi(W)+\frac1n)/(1-\varepsilon)$ for all $W$, $n$ and $\varepsilon$.3033Capacity satisfies \textup{(i)--(iii)}, and it is the least function that does: $\Phi\ge C$ for every such3034$\Phi$.3035\end{theorem}3036 3037\begin{proof}3038If $(e,d)$ is an $(M,\varepsilon)$-code for $W^{\otimes n}$ then by (iii), (i) and (ii),3039$(1-\varepsilon)\log M-1\le\Phi(d\circ W^{\otimes n}\circ e)\le\Phi(W^{\otimes n})\le n\Phi(W)$. Capacity satisfies (i) and3040(ii) by \cref{prop:capacity}, and (iii) by Fano's inequality with a uniform input. Finally, by3041\cref{thm:rank} the left side of the displayed bound tends to $C(W)$, so $C(W)\le\Phi(W)/(1-\varepsilon)$ for3042every $\varepsilon$.3043\end{proof}3044 3045The first half of the theorem, the bound, is the converse and is formal. The second half, minimality, is3046the coding theorem: it says that no obstruction of this general kind is sharper than mutual information,3047and it rests on Feinstein's lemma. Stated this way Shannon's theorem is the assertion that a certain3048extremal problem over monotone functions has the explicit solution $\max_pI(p,W)$.3049 3050\section{Separation}3051 3052In \cref{fig:shannon} the composite factors through the finite set $[M]$. The source is first turned into3053one of $M$ messages without reference to the channel, and the channel is used to send one of $M$ messages3054without reference to the source. \Cref{thm:shannon1,thm:converse} together say that for an ergodic source and3055a memoryless channel nothing is lost, in the limit, by insisting on this factorization. That is the3056source--channel separation theorem. It is a statement about limits and about stable systems. For3057non-ergodic sources or channels, where the information density does not concentrate, separation can fail3058\cite{VVS95}, and in networks with several senders and receivers it fails in general.3059 3060\section{Polarization: the martingale returns}3061 3062Feinstein's lemma finds a code by search. For a large class of channels there is an explicit construction,3063due to Ar\i kan, whose analysis is a martingale argument.3064 3065Let $W\colon\{0,1\}\to Y$ be a channel with binary input and write $I(W)$ for its mutual information with3066uniform input. Take two independent uses of $W$ and feed them $x_1=u_1\oplus u_2$ and $x_2=u_2$, where $u_1,u_2$ are3067independent uniform bits. This defines two new binary-input channels:3068\[ W^-\colon u_1\mapsto(y_1,y_2),\qquad W^+\colon u_2\mapsto(y_1,y_2,u_1). \]