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

2929 2930\begin{lemma}[Retractions compose]\label{lem:compose}2931\Sob Let $(e_s,d_s)$ be an $(M,\varepsilon_1)$-compression of a finite probability space $(X,p)$ in the sense of2932\cref{def:compression}, and $(e_c,d_c)$ an $(M,\varepsilon_2)$-code for $W\colon U\to V$ in the sense of2933\cref{def:code}. Then for $x$ drawn from $p$, sent as $e_c(e_s(x))$ through $W$ and decoded by2934$d_s\circ d_c$, the result equals $x$ with probability at least $1-\varepsilon_1-\varepsilon_2$.2935\end{lemma}2936 2937\begin{proof}2938With probability at least $1-\varepsilon_1$ the point $x$ satisfies $d_s(e_s(x))=x$. Whatever the message2939$j=e_s(x)$ is, the channel code returns it with probability at least $1-\varepsilon_2$.2940\end{proof}2941 2942The second step is where the maximal-error criterion of \cref{def:code} is used. The compression may2943concentrate the source on a few messages, and the channel code must work for each of them. A code that is2944good only on average over messages would not compose with an arbitrary source (\cref{exer:average}). This is2945why Feinstein's formulation suits Khinchin's proof.2946 2947\begin{figure}[ht]\centering2948\begin{tikzpicture}[x=0.95cm,y=1cm]2949  \node[ogbox] (mu) at (0,0) {$\mu_n$};2950  \node[ogbox] (es) at (1.9,0) {$e_s$};2951  \node[ogbox] (ec) at (4.1,0) {$e_c$};2952  \node[ogbox] (W) at (6.7,0) {$W_n$};2953  \node[ogbox] (dc) at (9.1,0) {$d_c$};2954  \node[ogbox] (ds) at (11.3,0) {$d_s$};2955  \draw[fw] (mu) -- (es);2956  \draw[fw] (es) -- node[above=2pt,lab,black]{$[M]$} (ec);2957  \draw[fw] (ec) -- node[above=2pt,lab,black]{$A^{n+m}$} (W);2958  \draw[fw] (W) -- node[above=2pt,lab,black]{$B^n$} (dc);2959  \draw[fw] (dc) -- node[above=2pt,lab,black]{$[M]$} (ds);2960  \draw[fw] (ds) -- node[above=2pt,lab,black]{$A_0^n$} (12.9,0);2961\end{tikzpicture}2962\caption{Shannon's first theorem as a composite of two approximate retractions. The middle three boxes are2963within $\varepsilon$ of the identity of $[M]$ by Feinstein's lemma; the outer two are within $\varepsilon$ of the2964identity on $\mu_n$-typical blocks by McMillan's theorem.}\label{fig:shannon}2965\end{figure}2966 2967\begin{theorem}[Shannon's first theorem]\label{thm:shannon1}2968\Scl[\cite{Sha48,Fei54,Khi56}] Let $\nu$ be a channel as in \cref{thm:feinsteinmem}, with ergodic capacity $C$, and let2969$[A_0,\mu]$ be an ergodic source with entropy $H_0<C$. For every $\varepsilon>0$ and all large $n$ there are maps2970$A_0^n\to A^{n+m}$ and $B^n\to A_0^n$ such that a block of $n$ letters from the source, encoded, transmitted and2971decoded, is recovered with probability at least $1-\varepsilon$.2972\end{theorem}2973 2974\begin{proof}2975Choose $\delta>0$ with $H_0+\delta<C-\delta$ and put $M=2^{\lceil n(H_0+\delta)\rceil}$. By \cref{prop:corank} the block2976law $\mu_n$ has an $(M,\varepsilon/2)$-compression for large $n$. By \cref{thm:feinsteinmem} the block channel $W_n$2977has a $(2^{\lceil n(C-\delta)\rceil},\varepsilon/2)$-code for large $n$, and $2^{\lceil n(C-\delta)\rceil}\ge M$. Apply2978\cref{lem:compose}.2979\end{proof}2980 2981\section{The second theorem}2982 2983Khinchin's second theorem says that the code can be chosen so that the rate of transmission between the2984source and the received signal is as close as desired to the entropy $H_0$ of the source, or equivalently2985so that the equivocation per letter is small.2986 2987\begin{theorem}[Shannon's second theorem]\label{thm:shannon2}2988\Scl[\cite{Khi56}, \S16] Under the hypotheses of \cref{thm:shannon1}, for every $\varepsilon'>0$ there is a code for2989which the equivocation of the source block given the received block is less than $n\varepsilon'$.2990\end{theorem}2991 2992\begin{proof}2993Take the code of \cref{thm:shannon1}. The received block determines the decoded block, which differs from2994the source block with probability at most $\varepsilon$. By Fano's inequality (\cref{lem:feinstein3})2995the equivocation is at most $1+\varepsilon\,n\log|A_0|$.2996\end{proof}2997 2998In the language of \cref{ch:inequalities}: a morphism within $\varepsilon$ of having a left inverse has2999equivocation at most $\hb(\varepsilon)+\varepsilon\log(\text{size})$. The second theorem is the first theorem passed3000through Fano's inequality, and Khinchin proves it that way.3001 3002\section{The converse, and the two kinds of statement}3003 3004\begin{theorem}[Converse]\label{thm:converse}3005\Scl[\cite{Fan61}] Let $W$ be a memoryless channel with capacity $C$ and $\mu$ a stationary source with entropy3006$H_0>C$. For every $n$ and every pair of maps $A_0^n\to A^n$, $B^n\to A_0^n$ the probability $P_e$ that a block is3007not recovered satisfies3008\[ P_e\ \ge\ \frac{H_0-C-1/n}{\log|A_0|}. \]3009\end{theorem}3010 3011\begin{proof}3012Let $\theta$ be the source block and $\hat\theta$ the decoded block. Then3013$nH_0\le H(\theta)=I(\theta;\hat\theta)+H(\theta\st\hat\theta)\le nC+1+P_e\,n\log|A_0|$, by data processing, \cref{thm:dmc}3014and Fano's inequality.3015\end{proof}3016 3017Compare the ingredients. The converse uses the chain rule, the data-processing inequality, the3018additivity of capacity over independent uses, and Fano's inequality. Each of these is a property of a3019function on morphisms: functoriality, monotonicity under composition, additivity under tensor, continuity3020at identities. The direct theorem uses McMillan's theorem and Feinstein's lemma, which assert that certain3021morphisms exist. The first kind of statement is what category theory handles well, and the converse can be3022stated for any function with those properties.3023 3024\begin{theorem}[A universal property of capacity]\label{thm:universal}3025\Sob Let $\Phi$ assign a number in $[0,\infty)$ to each morphism of $\FinStoch$ so that3026\begin{enumerate}[label=(\roman*)]3027\item $\Phi(g\circ f)\le\min\{\Phi(f),\Phi(g)\}$;3028\item $\Phi(f\otimes g)\le\Phi(f)+\Phi(g)$;