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 2249–2348 of 4249. Source text is displayed literally.
2249$\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}2309 2310Thus $\mu_n$ is close to a uniform distribution, but only on the exponential scale: the ratio of2311probabilities is $2^{o(n)}$, not close to $1$, and $\mu_n$ is in general far from $u_S$ in total variation.2312Gromov has made this scale into a framework \cite{Gro13}. He considers the category of finite probability2313spaces and measure-preserving maps, defines an asymptotic equivalence between sequences of such spaces2314that ignores sets of small measure and subexponential factors, and reads the law of large numbers as the2315statement that the powers $P^{\otimes n}$ are asymptotically equivalent to the uniform spaces on $2^{nH(P)}$2316points. Entropy is then the isomorphism from the semigroup of asymptotic classes, under tensor product, to2317$[0,\infty)$. McMillan's theorem extends the first half of this from powers of one space to the block laws of2318any ergodic source.2319 2320\section*{Notes}2321 2322McMillan's theorem is \cite{McM53}; Khinchin's proof is \cite[\S\S5--8]{Khi56}. The almost sure version is2323due to Breiman \cite{Bre57}, with the countable case by Chung \cite{Chu61}; the sandwich proof is2324\cite{AC88}. Textbook accounts are in \cite{Bil65,Gra11,CT06}. The counting theorem and its use for coding2325go back to Shannon \cite{Sha48}. The second-order behaviour in \cref{exer:second} is due to Strassen. For2326the non-ergodic case and the information spectrum see \cite{Han03}.2327 2328\section*{Exercises}2329 2330\begin{exercise}2331For independent letters with distribution $p$, derive the $E$ property from Chebyshev's inequality, with the2332bound $\Prob(|\frac1ni_n-H|\ge\varepsilon)\le\sigma^2/(n\varepsilon^2)$ where $\sigma^2$ is the variance of $-\log p(x_0)$.2333Compute $\sigma^2$ for bits with $\Prob(1)=0.2$.2334\end{exercise}2335 2336\begin{exercise}2337For a stationary Markov source show that $g_k=g_1$ for all $k\ge1$, and deduce McMillan's theorem from2338\cref{cor:meanergodic} alone.2339\end{exercise}2340 2341\begin{exercise}2342Prove \cref{cor:typical} and \cref{prop:uniform}.2343\end{exercise}2344 2345\begin{exercise}\label{exer:mixcount}2346For the source of \cref{ex:mixture} show that $\frac1n\log N_n(\lambda)\to\hb(0.1)$ for $\lambda<\tfrac12$ and $\to1$ for2347$\lambda>\tfrac12$.2348\end{exercise}