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

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 3149\begin{exercise}\label{exer:bec}3150For the erasure channel prove that $W^-$ and $W^+$ are erasure channels with probabilities $2e-e^2$ and3151$e^2$. Let $f(e)=\sqrt{e(1-e)}$. Show that $\tfrac12\bigl(f(2e-e^2)+f(e^2)\bigr)\le\tfrac{\sqrt3}{2}f(e)$, and deduce3152\cref{thm:polar} for erasure channels without any martingale theorem.3153\end{exercise}3154%% ---- end ch/11-shannon.tex ----3155%% ---- begin ch/12-rates.tex ----3156\chapter{Rates and Spectra}\label{ch:rates}3157 3158Entropy and capacity were obtained in the last chapters as limits: growth rates of the sizes of sets that3159are approximate retracts of, or admit approximate retractions onto, tensor powers. Two features of the3160definitions did the work, the tolerance $\varepsilon$ and the passage to the limit. This chapter asks what3161each contributes. Without the tolerance, the limits still exist but are governed by a family of invariants3162and not by one number. Strassen's theory of asymptotic spectra describes such families. In the infinite3163setting of ergodic theory, on the other hand, the tolerance is not needed at all. None of this is in3164Khinchin; it is the context in which his theorems now sit.3165 3166\section{Coding without error}3167 3168Let $W\colon X\to Y$ be a stochastic matrix. Two inputs are \term{confusable} if some output has positive3169probability under both. The \term{confusability graph} $G_W$ has vertex set $X$ and an edge between3170confusable inputs. A $(M,0)$-code is a set of $M$ pairwise non-confusable inputs, so3171$M^*(W,0)=\alpha(G_W)$, the independence number, and for $n$ uses3172$M^*(W^{\otimes n},0)=\alpha(G_W^{\boxtimes n})$, where $\boxtimes$ is the strong product of graphs.3173 3174\begin{definition}[Shannon]3175The \term{zero-error capacity} of $W$ is $C_0(W)=\lim_n\frac1n\log\alpha(G_W^{\boxtimes n})=\log\Theta(G_W)$.3176\end{definition}3177 3178\begin{example}\label{ex:pentagon}3179Let $X=Y=\Z/5$ and let $W$ send $x$ to $x$ or $x+1$ with probability $\tfrac12$ each. Its capacity is3180$\log5-1\approx1.322$. Its confusability graph is the pentagon $C_5$, with $\alpha(C_5)=2$, so one use carries one