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

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}2829 2830Feinstein's lemma is \cite{Fei54}; his book \cite{Fei58} and Khinchin's Chapter~IV \cite{Khi56} extend it to2831channels with memory. The one-shot form with the information density is from the information-spectrum2832literature \cite{VH94,Han03}; see \cite{PW25} for a textbook treatment and for comparison with the2833random-coding bounds. The strong converse is due to Wolfowitz \cite{Wol57,Wol78}. Information stability was2834introduced by Dobrushin \cite{Dob59}.2835 2836\section*{Exercises}2837 2838\begin{exercise}2839Prove \eqref{eq:QE}.2840\end{exercise}2841 2842\begin{exercise}\label{exer:hamming}2843For the binary symmetric channel with flip probability $\delta$ and uniform inputs on $\{0,1\}^n$, show that2844$i(x;y)=n+d\log\delta+(n-d)\log(1-\delta)$ with $d$ the Hamming distance, so that the sets $E_x$ are Hamming2845balls. For $n=7$, $\delta=0.01$ and $M=16$, find the best error guaranteed by \cref{thm:feinstein} and compare2846it with the error probability of the $(7,4)$ Hamming code.2847\end{exercise}2848 2849\begin{exercise}2850Compute $M^*(W,\varepsilon)$ for the identity channel on a set of $k$ elements and for a channel that ignores2851its input, for all $\varepsilon\in[0,1)$.2852\end{exercise}2853 2854\begin{exercise}2855Show that allowing a stochastic encoder $e\colon[M]\to X$ in \cref{def:code} does not increase2856$M^*(W,\varepsilon)$. Give an example in which a stochastic decoder achieves a smaller maximal error than2857every deterministic decoder for the same codewords.2858\end{exercise}2859 2860\begin{exercise}2861Let $W$ be the binary erasure channel with erasure probability $e$. Show that a set of $M$ distinct2862codewords of length $n$, decoded by returning the unique codeword consistent with the unerased positions2863when there is one, has maximal error at most $\varepsilon$ provided every codeword is, with probability2864$1-\varepsilon$, distinguished from all others by the unerased positions. Deduce that linear codes of rate2865below $1-e$ exist with small error, by counting.2866\end{exercise}2867%% ---- end ch/10-feinstein.tex ----2868%% ---- begin ch/11-shannon.tex ----2869\chapter{Shannon's Theorems}\label{ch:shannon}2870 2871Everything is now in place. McMillan's theorem makes a long block from an ergodic source an approximate2872retract of a set of $2^{nH}$ points. Feinstein's lemma makes a set of $2^{nC}$ points an approximate retract of2873a long block of channel uses. If $H<C$ the first set fits inside the second, and the composite of the two2874retractions transmits the source through the channel. This is Shannon's theorem as Khinchin proves it in2875his last chapter. We present it in that form, add the converse, which Khinchin does not treat, and observe2876that the two halves of the theorem are of different kinds. The chapter ends with polar codes, where the2877martingale of \cref{ch:martingales} returns in a new role.2878 2879\section{Coding without noise}2880