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

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.3109\end{example}3110 3111Three things in this construction belong to the themes of this book. The transform is a string diagram3112built from copying, a deterministic isomorphism, and $W\otimes W$; its $n$-fold iterate is a tensor power of3113one small diagram. The conservation law is the chain rule along an isomorphism, that is, functoriality. And3114the proof of polarization needs only the orthogonality of the increments of a martingale, which is the3115statement that the projections of \cref{ch:martingales} are orthogonal projections. The result is an explicit3116$\varepsilon$-retraction of $W^{\otimes N}$ onto a set of about $2^{NI(W)}$ points. Khinchin brought the martingale3117into information theory to handle the source. Half a century later it turned out to construct the code.3118 3119\section*{Notes}3120 3121Shannon's theorems are in \cite{Sha48}. Khinchin's proofs are \cite[Ch.~V]{Khi56}; his first paper treats3122noiseless coding \cite[\S5]{Khi53}. Kraft's inequality is \cite{Kra49}, extended to uniquely decodable codes3123by McMillan \cite{McM56}; optimal codes are due to Huffman \cite{Huf52}. Fano's inequality and the converse3124are in \cite{Fan61}; see \cite{CT06,CK11,PW25}. The failure of separation for non-ergodic systems is studied in3125\cite{VVS95}. Polar codes are due to Ar\i kan \cite{Ari09}; the rate of polarization is in \cite{AT09}.3126 3127\section*{Exercises}3128 3129\begin{exercise}3130Find an optimal prefix code for $p=(0.4,0.3,0.2,0.1)$ and compare its expected length with $H(p)$.3131\end{exercise}3132 3133\begin{exercise}3134Show that $L^*(p)=H(p)$ iff every $p(x)$ is a power of $\tfrac12$.3135\end{exercise}3136 3137\begin{exercise}\label{exer:average}3138Give an example of a channel code with small error probability on average over uniformly chosen messages,3139and a compression of a source, whose composite fails with probability close to $1$. How can the code be3140repaired?3141\end{exercise}3142 3143\begin{exercise}3144Let $r_+(W)$ be the least size of a set through which $W$ factors in $\FinStoch$. Show that3145$\Phi=\log r_+$ satisfies the hypotheses of \cref{thm:universal}, state the bound it gives, and give a channel3146with $\Phi(W)>C(W)$. Does $\Phi(W)=\log\min\{|X|,|Y|\}$ satisfy the hypotheses?3147\end{exercise}3148