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

2729$\Prob[\frac1ni\le C-\frac\delta2]\to0$. Apply \cref{thm:feinstein} with $\log M=\lceil n(C-\delta)\rceil$ and2730$\gamma=n\delta/2-1$.2731\end{proof}2732 2733\begin{example}\label{ex:feinsteinbsc}2734For the binary symmetric channel with flip probability $0.11$ the capacity is $0.500$. With uniform inputs,2735rate $0.25$ and $\gamma=n/8$, the error guaranteed by \cref{thm:feinstein} is $0.032$ at $n=200$,2736$3\times10^{-5}$ at $n=1000$, and $2\times10^{-19}$ at $n=5000$. At short lengths the bound is weak2737(\cref{exer:hamming}).2738\end{example}2739 2740\section{Channels with memory}2741 2742Let $\nu$ be a stationary channel without anticipation and of finite memory $m$. Then the law of the output2743block $y_1\dots y_n$ depends only on the input letters $x_{1-m},\dots,x_n$, and this defines a morphism2744\[ W_n\colon A^{n+m}\longrightarrow B^n \]2745of $\FinStoch$. The first $m$ input letters serve to put the channel into a known condition.2746 2747\begin{theorem}[Feinstein's fundamental lemma]\label{thm:feinsteinmem}2748\Scl[\cite{Khi56}, Ch.~IV; with the hypotheses of \cref{thm:ergodicchannel}] Let $\nu$ be stationary, without2749anticipation, 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}