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 2681–2780 of 4249. Source text is displayed literally.
2681Fix a distribution $P$ on $X$ and let $Q=W\circ P$ be the output distribution. The \term{information density}2682is2683\[ i(x;y)=\log\frac{W(y\st x)}{Q(y)}, \]2684a random variable on $X\times Y$ under the joint law $P\rtimes W$, with mean $I(P,W)$.2685 2686\section{The one-shot lemma}2687 2688\begin{theorem}[Feinstein]\label{thm:feinstein}2689\Scl[\cite{Fei54}; in this form see \cite{VH94,PW25}] For every distribution $P$ on $X$, every integer $M\ge1$ and2690every $\gamma>0$, there is an $(M,\varepsilon)$-code for $W$ with2691\[ \varepsilon=\Prob\bigl[i(X;Y)\le\log M+\gamma\bigr]+2^{-\gamma}, \]2692provided this number is less than $1$.2693\end{theorem}2694 2695\begin{proof}2696For $x\in X$ let $E_x=\{y:i(x;y)>\log M+\gamma\}$, the set where $W(y\st x)>M2^\gamma Q(y)$. Summing this inequality2697over $E_x$ gives2698\begin{equation}\label{eq:QE}2699 Q(E_x)\le\frac{2^{-\gamma}}{M}.2700\end{equation}2701Choose codewords one at a time. Given $x_1,\dots,x_k$ and $D_1,\dots,D_k$, pick any $x_{k+1}$ with2702\[ W\bigl(E_{x_{k+1}}\setminus(D_1\cup\dots\cup D_k)\,\big|\,x_{k+1}\bigr)\ge1-\varepsilon \]2703and let $D_{k+1}=E_{x_{k+1}}\setminus(D_1\cup\dots\cup D_k)$. Each new set is nonempty and disjoint from the earlier2704ones, so the procedure stops, say after $N$ steps, with an $(N,\varepsilon)$-code. Let $D$ be the union of its2705decoding sets.2706 2707At that point every $x\in X$ satisfies $W(E_x\setminus D\st x)<1-\varepsilon$. Averaging over $P$,2708\[ \Prob\bigl[i(X;Y)>\log M+\gamma,\ Y\notin D\bigr]<1-\varepsilon, \]2709and therefore, by \eqref{eq:QE} applied to each codeword,2710\[ \Prob\bigl[i(X;Y)>\log M+\gamma\bigr]<1-\varepsilon+Q(D)\le1-\varepsilon+\frac NM\,2^{-\gamma}. \]2711Rearranged, $\varepsilon<\Prob[i\le\log M+\gamma]+\frac NM2^{-\gamma}$. Comparing with the definition of $\varepsilon$ gives $N>M$.2712Keep the first $M$ codewords.2713\end{proof}2714 2715The proof is a greedy construction and one counting estimate. The estimate \eqref{eq:QE} says that a2716decoding set on which the likelihood ratio is large has small probability under the output distribution,2717so that many of them fit. The construction uses nothing about the structure of $X$, $Y$ or $W$.2718 2719\section{Memoryless channels}2720 2721\begin{theorem}\label{thm:feinsteindmc}2722\Scl[\cite{Fei54}] Let $W$ be a stochastic matrix with capacity $C$. For all $\delta,\varepsilon>0$ and all2723large $n$ there is a $(2^{\lceil n(C-\delta)\rceil},\varepsilon)$-code for $W^{\otimes n}$.2724\end{theorem}2725 2726\begin{proof}2727Let $p$ attain the capacity and take $P=p^{\otimes n}$. The information density of $n$ uses is a sum of $n$2728independent copies of the one-letter density, with mean $C$. By the weak law of large numbers2729$\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] \]