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

2661the first proof that was accepted as rigorous, by a different route: he showed directly that a channel2662admits many input words whose output distributions are almost disjointly supported. Khinchin calls this2663Feinstein's fundamental lemma, proves it for stationary channels with finite memory, and derives Shannon's2664theorems from it. This chapter proves the lemma in its modern one-shot form, which takes a page, recovers2665Khinchin's version from it with McMillan's theorem, and then reads the statement as one about2666retractions.2667 2668\section{Codes}2669 2670\begin{definition}\label{def:code}2671Let $W\colon X\to Y$ be a morphism of $\FinStoch$ and $0\le\varepsilon<1$. An \term{$(M,\varepsilon)$-code} for $W$2672consists of codewords $x_1,\dots,x_M\in X$ and pairwise disjoint decoding sets $D_1,\dots,D_M\subseteq Y$ with2673\[ W(D_j\st x_j)\ge1-\varepsilon\qquad\text{for all }j. \]2674$M^*(W,\varepsilon)$ is the largest $M$ for which one exists.2675\end{definition}2676 2677Khinchin calls the codewords a \emph{distinguishable group} of sequences. Note that the requirement is on2678each codeword separately; this is the maximal-error criterion, and it does not refer to any distribution on2679messages.2680 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.