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 2609–2708 of 4249. Source text is displayed literally.
2609\term{joining} of the two sources in the sense of ergodic theory \cite{Gla03}. Conversely, by2610disintegration, every joining arises from a stationary channel, unique up to $\mu$-null sets. So the2611morphisms from $(\AZ,\mu)$ to $(\BZ,\eta)$ in the equivariant version of the category $\Krn$ of2612\cref{ch:martingales} are the joinings, composition is the relatively independent joining over the middle2613factor, and the dagger reverses a joining. The reverse of $\nu$ with respect to $\mu$ is the \term{backward2614channel} $\nu^\dagger\colon\BZ\to\AZ$, which gives the conditional law of the input given the output.2615 2616The rate is symmetric, $R(\mu,\nu)=R(\eta,\nu^\dagger)$. The two conditional entropy rates are the noise2617$H(\omega)-H(\mu)$ of the channel and the \term{equivocation} $H(\omega)-H(\eta)=H(\mu)-R(\mu,\nu)$, which is the noise of2618the backward channel. Shannon's second theorem, in Khinchin's formulation, is a statement about the2619equivocation.2620 2621\section*{Notes}2622 2623Khinchin's definitions and the two theorems on the compound source are \cite[Ch.~III]{Khi56}. The2624insufficiency of his finite-memory condition and its repair are discussed in \cite{Tak58,Fei59,Bre60};2625ergodic properties of channels with infinite memory are treated by Adler \cite{Adl61}, and the modern theory2626is in Gray's book \cite{Gra11}, where the compound source is called the hookup. The equality of ergodic and2627stationary capacity is due to Parthasarathy \cite{Par61} and Breiman \cite{Bre60}; see also2628\cite{Ned57,Jac59}. For joinings see \cite{Gla03}.2629 2630\section*{Exercises}2631 2632\begin{exercise}2633Derive the capacities of the erasure channel and the Z-channel in \cref{ex:channels}.2634\end{exercise}2635 2636\begin{exercise}2637Show that the composite of binary symmetric channels with flip probabilities $\delta_1,\delta_2$ is binary symmetric2638with flip probability $\delta_1(1-\delta_2)+\delta_2(1-\delta_1)$. Compute the capacity for $\delta_1=\delta_2=0.1$ and compare with2639\cref{prop:capacity}(ii).2640\end{exercise}2641 2642\begin{exercise}2643For the channel of \cref{ex:gap} and any stationary source, compute $H(\eta)$, $H(\omega)$ and $R(\mu,\nu)$.2644\end{exercise}2645 2646\begin{exercise}\label{exer:sumchannel}2647Prove \cref{prop:capacity}(iii) in full, and show that $C(W\oplus W')=\log\bigl(2^{C(W)}+2^{C(W')}\bigr)$ for the channel2648$W\oplus W'$ whose input and output alphabets are the disjoint unions.2649\end{exercise}2650 2651\begin{exercise}2652Show that the deterministic natural families $A^n\to B^n$ are the causal functions2653$y_n=f_n(x_1,\dots,x_n)$, and that the kernel $y_n=x_{n+1}$ on one-sided sequences is not induced by a natural2654family.2655\end{exercise}2656%% ---- end ch/09-channels.tex ----2657%% ---- begin ch/10-feinstein.tex ----2658\chapter{Feinstein's Lemma}\label{ch:feinstein}2659 2660Shannon's proof of his theorem for noisy channels chose codewords at random and averaged. Feinstein gave2661the 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, \]