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 2749–2848 of 4249. Source text is displayed literally.
2749anticipation, of finite memory $m$ and of finite output memory, with ergodic capacity $C$. For all2750$\delta,\varepsilon>0$ and all large $n$ there is a $(2^{\lceil n(C-\delta)\rceil},\varepsilon)$-code for $W_n$.2751\end{theorem}2752 2753\begin{proof}2754Choose an ergodic source $\mu$ with $R(\mu,\nu)>C-\delta/4$ and let $P$ be its block law on $A^{n+m}$. The2755information density of $W_n$ is2756\[ i_n=-\log\mu(x_{1-m}\dots x_n)-\log\eta(y_1\dots y_n)+\log\omega(x_{1-m}\dots x_n,\,y_1\dots y_n). \]2757The sources $\mu$, $\eta$ and $\omega$ are ergodic by \cref{thm:ergodicchannel}, so by \cref{thm:mcmillan} the three2758terms divided by $n$ converge in probability to $H(\mu)$, $H(\eta)$ and $-H(\omega)$; the $m$ extra letters do not2759affect the limits. Hence $\frac1ni_n\to R(\mu,\nu)$ in probability, and \cref{thm:feinstein} applies as in the2760memoryless case.2761\end{proof}2762 2763This is the one place in the whole development where the ergodicity of the compound source is needed, and2764it is the reason the gap discussed in \cref{ch:channels} matters. Khinchin's own proof does not pass2765through a one-shot statement. It builds the distinguishable sequences directly inside the typical sets2766supplied by McMillan's theorem, using the inequalities of \cref{lem:partial,lem:feinstein3}, and takes ten2767pages. The idea is the same.2768 2769The proof shows what is really required of the channel and the source: that the normalized information2770density converge in probability. A pair with this property is called \term{information stable}, after2771Dobrushin \cite{Dob59}. For an arbitrary sequence of channels $W_n$ the capacity is the supremum, over input2772processes, of the largest number that the normalized information density exceeds with probability tending2773to one \cite{VH94}; stationarity, ergodicity and memory conditions are sufficient conditions for this2774number to be a limit of mutual informations.2775 2776\section{Codes as retractions}2777 2778A code is a pair of maps $e\colon[M]\to X$ and $d\colon Y\to[M]$: $e$ lists the codewords, and $d$ sends $D_j$ to2779$j$. The condition of \cref{def:code} says that every diagonal entry of the stochastic matrix2780\[ [M]\xrightarrow{\ e\ }X\xrightarrow{\ W\ }Y\xrightarrow{\ d\ }[M] \]2781is at least $1-\varepsilon$. For $\varepsilon=0$ this says $d\circ W\circ e=\id$: the identity of $[M]$ is a retract of2782$W$. In general the composite is within $\varepsilon$ of the identity, in the total variation distance of2783\cref{thm:enriched}, uniformly over inputs.2784 2785\begin{definition}2786The \term{$\varepsilon$-rank} of $W$ is $M^*(W,\varepsilon)$, the size of the largest finite set whose identity is an2787$\varepsilon$-retract of $W$.2788\end{definition}2789 2790\begin{theorem}[Capacity is the asymptotic $\varepsilon$-rank]\label{thm:rank}2791\Scl[\cite{Fei54,Wol57}] For a stochastic matrix $W$ and every $\varepsilon\in(0,1)$,2792\[ \lim_{n\to\infty}\frac1n\log M^*(W^{\otimes n},\varepsilon)=C(W). \]2793\end{theorem}2794 2795\begin{proof}2796The lower bound is \cref{thm:feinsteindmc}. For the upper bound in the limit $\varepsilon\to0$, let the message2797$J$ be uniform on $[M]$, sent as $e(J)$ and decoded as $\hat J$. The probability of error is at most2798$\varepsilon$, so by Fano's inequality (\cref{lem:feinstein3}) and data processing,2799\[ \log M=I(J;\hat J)+H(J\st\hat J)\le I(X^n;Y^n)+1+\varepsilon\log M\le nC+1+\varepsilon\log M. \]2800Thus $\frac1n\log M^*(W^{\otimes n},\varepsilon)\le(C+\frac1n)/(1-\varepsilon)$. That the limit is $C$ for every fixed2801$\varepsilon<1$, and not merely as $\varepsilon\to0$, is Wolfowitz's strong converse.2802\end{proof}2803 2804Set this beside \cref{prop:corank}. For an ergodic source $\mu$ and a memoryless channel $W$,2805\begin{align*}2806 H(\mu)&=\lim_n\tfrac1n\log\min\{M:\ (A^n,\mu_n)\text{ is an $\varepsilon$-retract of }[M]\},\\2807 C(W)&=\lim_n\tfrac1n\log\max\{M:\ [M]\text{ is an $\varepsilon$-retract of }W^{\otimes n}\},2808\end{align*}2809and neither limit depends on $\varepsilon\in(0,1)$. Entropy is how large a set is needed to hold the source;2810capacity is how large a set the channel can hold. Both are defined by the structure of an enriched2811monoidal category alone: tensor powers, composition, and the distance to an identity.2812 2813For a linear map the largest identity that is a retract of it and the smallest identity through which it2814factors have the same dimension, the rank. For stochastic matrices the two exact notions are different2815and neither is well behaved under tensor product; the first is the zero-error capacity of \cref{ch:rates}.2816The tolerance $\varepsilon$, together with the passage to the limit, is what produces a single additive2817invariant.2818 2819\section{What the lemma is}2820 2821It should be said plainly what the categorical language has and has not done here. It has given the2822statement a form, a retraction up to $\varepsilon$, in which it composes with other statements of the same2823form; the next chapter uses this. It has not shortened the proof of \cref{thm:feinstein}, which is a2824counting argument about sets, and it does not construct the code, which is found by exhaustive search.2825Feinstein's lemma and McMillan's theorem are the two places where the theory touches the particular, and2826only the second has so far been dissolved into general statements.2827 2828\section*{Notes}2829 2830Feinstein's lemma is \cite{Fei54}; his book \cite{Fei58} and Khinchin's Chapter~IV \cite{Khi56} extend it to2831channels with memory. The one-shot form with the information density is from the information-spectrum2832literature \cite{VH94,Han03}; see \cite{PW25} for a textbook treatment and for comparison with the2833random-coding bounds. The strong converse is due to Wolfowitz \cite{Wol57,Wol78}. Information stability was2834introduced by Dobrushin \cite{Dob59}.2835 2836\section*{Exercises}2837 2838\begin{exercise}2839Prove \eqref{eq:QE}.2840\end{exercise}2841 2842\begin{exercise}\label{exer:hamming}2843For the binary symmetric channel with flip probability $\delta$ and uniform inputs on $\{0,1\}^n$, show that2844$i(x;y)=n+d\log\delta+(n-d)\log(1-\delta)$ with $d$ the Hamming distance, so that the sets $E_x$ are Hamming2845balls. For $n=7$, $\delta=0.01$ and $M=16$, find the best error guaranteed by \cref{thm:feinstein} and compare2846it with the error probability of the $(7,4)$ Hamming code.2847\end{exercise}2848