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

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 one3181bit without error. But $\alpha(C_5\boxtimes C_5)=5$: the five words $(i,2i)$ are pairwise non-confusable. So3182two uses carry $\log5$ bits, and $C_0\ge\tfrac12\log5\approx1.161$.3183\end{example}3184 3185\begin{theorem}\label{thm:zeroerror}3186\Scl[\cite{Sha56,Lov79,Hae79,Alo98}] $\Theta(C_5)=\sqrt5$, so the bound in \cref{ex:pentagon} is the zero-error3187capacity. In general $\Theta$ is not multiplicative under the strong product and not additive under3188disjoint union: there are graphs with $\Theta(G\boxtimes H)>\Theta(G)\,\Theta(H)$ and with3189$\Theta(G\sqcup H)>\Theta(G)+\Theta(H)$. No algorithm is known that computes $\Theta$.3190\end{theorem}3191 3192Compare with \cref{prop:capacity}. Capacity is additive under tensor product, satisfies the sum formula of3193\cref{exer:sumchannel}, and is the solution of a convex optimization problem. Zero-error capacity has none of these3194properties. The exact rank of a stochastic matrix, in the sense of the largest identity that is a retract3195of it, does not become a homomorphism even after regularization.3196 3197\section{Asymptotic spectra}3198 3199Strassen found the right framework for regularized quantities of this kind while studying the complexity of3200matrix multiplication. Let $S$ be a commutative semiring containing the natural numbers, with a preorder3201$\le$ compatible with addition and multiplication, restricting to the usual order on $\N$, and such that3202every element is bounded by a natural number times any nonzero element. Define the \term{rank}3203$R(a)=\min\{n\in\N:a\le n\}$ and the \term{subrank} $Q(a)=\max\{n\in\N:n\le a\}$, and their regularizations3204$\tilde R(a)=\lim_nR(a^n)^{1/n}$ and $\tilde Q(a)=\lim_nQ(a^n)^{1/n}$. The \term{asymptotic spectrum} $\mathbf{X}(S)$ is3205the set of monotone semiring homomorphisms $S\to\R_{\ge0}$.3206 3207\begin{theorem}[Strassen]\label{thm:strassen}3208\Sli[\cite{Str88}] $\mathbf{X}(S)$ is a compact Hausdorff space, and for every $a\in S$,