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

2209 2210\begin{theorem}[Shannon--McMillan--Breiman]\label{thm:SMB}2211\Scl[\cite{Bre57,Chu61,AC88}] For an ergodic source, $\frac1ni_n\to H(\mu)$ almost surely. The same holds for2212countable alphabets when $H_1<\infty$.2213\end{theorem}2214 2215Breiman's proof combines the almost sure forms of the two convergence theorems with a maximal inequality2216for $\sup_kg_k$, of which \cref{lem:tail} is the distributional part; Algoet and Cover later gave a proof by2217sandwiching $i_n$ between Markov approximations. The theorem extends to actions of amenable groups2218\cite{OW83,Lin01}. For the coding theorems convergence in probability is all that is needed.2219 2220\section{Typical sets and the counting theorem}2221 2222Fix $\varepsilon>0$ and let $T_n^\varepsilon$ be the set of blocks $C$ of length $n$ with2223$2^{-n(H+\varepsilon)}\le\mu_n(C)\le2^{-n(H-\varepsilon)}$, where $H=H(\mu)$.2224 2225\begin{corollary}\label{cor:typical}2226\Scl For an ergodic source, $\mu_n(T_n^\varepsilon)\to1$; $|T_n^\varepsilon|\le2^{n(H+\varepsilon)}$ for all $n$; and2227$|T_n^\varepsilon|\ge(1-\delta)\,2^{n(H-\varepsilon)}$ as soon as $\mu_n(T_n^\varepsilon)\ge1-\delta$.2228\end{corollary}2229 2230For $0<\lambda<1$ let $N_n(\lambda)$ be the least number of blocks of length $n$ whose total probability is at2231least $\lambda$.2232 2233\begin{theorem}[Khinchin's Theorem 3]\label{thm:counting}2234\Scl[\cite{Sha48,Khi53}] For an ergodic source and every $\lambda\in(0,1)$,2235\[ \lim_{n\to\infty}\frac1n\log N_n(\lambda)=H(\mu). \]2236\end{theorem}2237 2238\begin{proof}2239For large $n$ the typical set has probability at least $\lambda$, so $N_n(\lambda)\le2^{n(H+\varepsilon)}$. Conversely let2240$S$ have probability at least $\lambda$. For large $n$, $\mu_n(S\cap T_n^\varepsilon)\ge\lambda/2$, and each block in2241$T_n^\varepsilon$ has probability at most $2^{-n(H-\varepsilon)}$, so $|S|\ge\frac\lambda2\,2^{n(H-\varepsilon)}$.2242\end{proof}2243 2244The limit does not depend on $\lambda$. That is the remarkable part of the statement, and it is special to2245the ergodic case.2246 2247\begin{example}\label{ex:counting}2248For independent bits with $\Prob(1)=0.2$ the entropy is $\hb(0.2)\approx0.7219$. The typical set with2249$\varepsilon=0.05$ has probability $0.468$ at $n=100$ and $0.952$ at $n=1000$. The rates $\frac1n\log N_n(\lambda)$2250are:2251\begin{center}\small2252\begin{tabular}{@{}lccc@{}}2253\toprule2254 & $\lambda=0.1$ & $\lambda=0.5$ & $\lambda=0.9$\\\midrule2255$n=100$ & $0.571$ & $0.684$ & $0.779$\\2256$n=1000$ & $0.683$ & $0.717$ & $0.748$\\2257\bottomrule2258\end{tabular}2259\end{center}2260The spread across $\lambda$ shrinks like $1/\sqrt n$ (\cref{exer:second}). For the Markov source of2261\cref{ex:markov}, $\E|\frac1ni_n-H|$ is $0.447$, $0.216$, $0.109$ at $n=4,16,64$.2262\end{example}2263 2264\begin{example}\label{ex:mixcount}2265For the non-ergodic source of \cref{ex:mixture} the limit depends on $\lambda$. At $n=1000$ the rate2266$\frac1n\log N_n(\lambda)$ is $0.463$ for $\lambda=0.25$ and $0.999$ for $\lambda=0.75$; the limits are $\hb(0.1)\approx0.469$ and $1$2267(\cref{exer:mixcount}). The entropy $0.7345$ of the source is not the answer to any counting question.2268\end{example}2269 2270So for a stationary source that is not ergodic, the entropy rate is not an operational quantity. The number2271of bits per letter needed to describe all but a fraction $\varepsilon$ of the blocks is a quantile of the2272distribution of $H(\mu_x)$, and to make $\varepsilon$ arbitrarily small one needs the essential supremum. This2273is the starting point of the information-spectrum method \cite{HV93,Han03}. Khinchin's restriction to ergodic2274sources is therefore not a convenience. His Theorem~4, on the best compression of a text by codes that may fail on a set of2275small probability, is false without it. For codes of variable length judged by their expected length the2276entropy rate remains the answer for every stationary source (\cref{ch:shannon}).2277 2278\section{The theorem as a statement about retractions}2279 2280\begin{definition}\label{def:compression}2281Let $(X,p)$ be a finite probability space and $0<\varepsilon<1$. An \term{$(M,\varepsilon)$-compression} of2282$(X,p)$ is a pair of maps $e\colon X\to[M]$ and $d\colon[M]\to X$, where $[M]=\{1,\dots,M\}$, such that2283$d(e(x))=x$ with probability at least $1-\varepsilon$. Let $M_*(p,\varepsilon)$ be the least $M$ for which one2284exists.2285\end{definition}2286 2287When $\varepsilon=0$ and $p$ has full support this says that $X$ is a retract of $[M]$, which happens iff2288$|X|\le M$. In general the set where $d\circ e$ is the identity has at most $M$ points, and any $M$ points2289can be made such a set, so $M_*(p,\varepsilon)=N(1-\varepsilon)$ in the notation above.2290 2291\begin{proposition}\label{prop:corank}2292\Srf[\cref{thm:counting}] For an ergodic source and every $\varepsilon\in(0,1)$,2293\[ \lim_{n\to\infty}\frac1n\log M_*(\mu_n,\varepsilon)=H(\mu). \]2294\end{proposition}2295 2296Up to $\varepsilon$, the space of blocks of length $n$ is a retract of a set with $2^{nH}$ points and of no2297smaller one. Entropy is the exponential growth rate of the approximate cardinality of $A^n$ as seen by2298$\mu$. In \cref{ch:feinstein} the dual notion, a finite set that is an approximate retract of a channel, will2299define capacity, and the two will be composed in \cref{ch:shannon}.2300 2301McMillan's theorem says more than \cref{prop:corank}, since it controls the probabilities of the typical2302blocks from both sides.2303 2304\begin{proposition}\label{prop:uniform}2305\Scl Let $\mu$ be ergodic and $\varepsilon>0$. For large $n$ there is a set $S\subseteq A^n$ with2306$\mu_n(S)\ge1-\varepsilon$ such that, for the uniform distribution $u_S$ on $S$ and all $C\in S$,2307\[ \Bigl|\frac1n\log\frac{\mu_n(C)}{u_S(C)}\Bigr|\le2\varepsilon+\frac1n . \]2308\end{proposition}