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

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}2349 2350\begin{exercise}\label{exer:second}2351For independent bits with $\Prob(1)=p<\tfrac12$, show that $N_n(\lambda)$ is attained by a set of sequences with2352the fewest ones, and use the central limit theorem to show that2353\[ \frac1n\log N_n(\lambda)=\hb(p)+\frac{\sigma\,\Phi^{-1}(\lambda)}{\sqrt n}+o\Bigl(\frac1{\sqrt n}\Bigr),\qquad\sigma=\sqrt{p(1-p)}\,\log\frac{1-p}{p}, \]2354where $\Phi$ is the standard normal distribution function. Compare with the table in \cref{ex:counting}.2355\end{exercise}2356%% ---- end ch/08-aep.tex ----2357\part{Channels and Coding}2358%% ---- begin ch/09-channels.tex ----2359\chapter{Channels}\label{ch:channels}2360 2361A channel, for Khinchin, is a family of probability measures $\nu_x$ on output sequences, one for each input2362sequence $x$. He imposes three conditions on it, stationarity, absence of anticipation and finite memory,2363connects it to a source, and proves that the resulting compound source is stationary and, when the source2364is ergodic, ergodic. In this chapter a channel is a morphism of the category $\Dyn$ of \cref{ch:sources}.2365The first of Khinchin's theorems becomes the statement that morphisms compose. The second is false as he2366states it, as was noticed within a few years, and the categorical formulation shows where the missing2367hypothesis has to go. We then study capacity as a function on morphisms.2368 2369\section{Khinchin's definitions}2370 2371\begin{definition}[\cite{Khi56}, \S9]\label{def:channel}2372A \term{channel} $[A,\nu,B]$ with input alphabet $A$ and output alphabet $B$ is a Markov kernel2373$\nu\colon\AZ\to\BZ$. It is2374\begin{itemize}2375\item \term{stationary} if $\nu\circ T=T\circ\nu$, that is, $\nu_{Tx}(TS)=\nu_x(S)$;2376\item \term{without anticipation} if for every $n$ the law of $(\dots,y_{n-1},y_n)$ under $\nu_x$ depends2377only on $(\dots,x_{n-1},x_n)$;2378\item of \term{finite memory} $m$ if for all $s\le t$ the law of $(y_s,\dots,y_t)$ under $\nu_x$ depends only on2379$(x_{s-m},\dots,x_t)$.2380\end{itemize}2381\end{definition}2382 2383A \term{memoryless} channel is given by a stochastic matrix $W\colon A\to B$ and2384$\nu_x=\bigotimes_nW(\,\cdot\st x_n)$: the output letters are independent given the input, and the $n$-th2385depends on $x_n$ alone. It has all three properties with $m=0$.2386 2387\section{Connecting a channel to a source}2388 2389By \cref{prop:dyn}, a stationary channel is a morphism $(\AZ,T)\to(\BZ,T)$ of $\Dyn$ and a stationary source is a2390state.2391 2392\begin{definition}2393The \term{compound source} of a source $[A,\mu]$ and a channel $[A,\nu,B]$ is the state2394\[ \omega=(\id\otimes\nu)\circ\cpy\circ\mu\quad\text{on }\AZ\times\BZ=(A\times B)^{\Z}, \]2395that is, $\omega(M\times N)=\int_M\nu_x(N)\,d\mu(x)$. Its second marginal $\eta=\nu\circ\mu$ is the \term{output source}.2396\end{definition}2397 2398\begin{figure}[ht]\centering2399\begin{tikzpicture}[x=1cm,y=1cm]2400  \node[ogbox] (mu) at (0,0) {$\mu$};2401  \node[dec] (c) at (1.6,0) {};2402  \node[ogbox] (nu) at (3.4,-0.65) {$\nu$};2403  \node[ogbox] (T1) at (5.4,0.65) {$T$};2404  \node[ogbox] (T2) at (5.4,-0.65) {$T$};2405  \draw[fw] (mu) -- (c);2406  \draw[fw] (c) |- (T1);2407  \draw[fw] (c) |- (nu);2408  \draw[fw] (nu) -- (T2);