Independent scholarship · Open accessThe monthly digest

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 3009–3108 of 4249. Source text is displayed literally.

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). \]3069The first sees $u_1$ through noise and through the unknown $u_2$; the second sees $u_2$ twice, given $u_1$.3070 3071\begin{proposition}\label{prop:polar}3072\Sli[\cite{Ari09}] $I(W^-)+I(W^+)=2I(W)$ and $I(W^-)\le I(W)\le I(W^+)$, with equality iff $I(W)\in\{0,1\}$.3073\end{proposition}3074 3075\begin{proof}[Proof of the first statement]3076The map $(u_1,u_2)\mapsto(x_1,x_2)$ is a bijection preserving the uniform distribution, so3077$I(u_1u_2;y_1y_2)=2I(W)$. By the chain rule this is $I(u_1;y_1y_2)+I(u_2;y_1y_2\st u_1)$, and the second term is3078$I(u_2;y_1y_2u_1)$ because $u_1$ and $u_2$ are independent.3079\end{proof}3080 3081Iterating the construction $n$ times produces $2^n$ channels $W^b$, indexed by sign sequences3082$b\in\{-,+\}^n$, from $2^n$ independent uses of $W$. Choose the signs by fair coin tosses and let3083$I_n=I(W^{b_1\dots b_n})$. By \cref{prop:polar}, $(I_n)$ is a martingale with values in $[0,1]$.3084 3085\begin{theorem}[Ar\i kan]\label{thm:polar}3086\Sli[\cite{Ari09}] For every $\delta>0$, as $n\to\infty$ the fraction of the $2^n$ channels $W^b$ with3087$I(W^b)>1-\delta$ tends to $I(W)$, and the fraction with $I(W^b)<\delta$ tends to $1-I(W)$.3088\end{theorem}3089 3090\begin{proof}3091The increments of a martingale are orthogonal in $L^2$, so3092$\sum_{k<n}\E(I_{k+1}-I_k)^2=\E(I_n-I_0)^2\le1$ and $\E(I_{k+1}-I_k)^2\to0$. On the other hand there is a function3093$\kappa(\delta)>0$, not depending on the output alphabet, such that $I(W)-I(W^-)\ge\kappa(\delta)$ whenever3094$\delta\le I(W)\le1-\delta$; this follows from Mrs.~Gerber's lemma \cite{WZ73,SSZ05}, and Ar\i kan argues instead3095with the Bhattacharyya parameter. By \cref{prop:polar} both possible increments have this absolute value, so3096the probability that $I_k\in[\delta,1-\delta]$ tends to zero. Since $\E I_n=I(W)$ and the middle range is3097asymptotically empty for every $\delta$, the probability that $I_n>1-\delta$ tends to $I(W)$.3098\end{proof}3099 3100A code is obtained by sending data bits on the indices $b$ with $I(W^b)$ near $1$, fixing the others, and3101decoding the bits in order; the block error probability tends to zero at any rate below $I(W)$3102\cite{Ari09,AT09}. For symmetric channels $I(W)$ is the capacity.3103 3104\begin{example}\label{ex:polar}3105For the erasure channel with erasure probability $e$ both new channels are erasure channels, with3106probabilities $2e-e^2$ and $e^2$. Starting from $e=\tfrac12$, the fraction of the $2^n$ channels with erasure3107probability below $0.01$ is $0.234$, $0.373$, $0.441$ and $0.473$ for $n=6,10,14,18$. It tends to the capacity3108$\tfrac12$. The mean erasure probability is $\tfrac12$ at every stage.