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

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);2409  \draw[fw] (T1) -- (7.0,0.65);2410  \draw[fw] (T2) -- (7.0,-0.65);2411  \node at (-1.2,-2.9) {$=$};2412  \node[ogbox] (mu2) at (0,-2.9) {$\mu$};2413  \node[ogbox] (T3) at (1.9,-2.9) {$T$};2414  \node[dec] (c2) at (3.5,-2.9) {};2415  \node[ogbox] (nu2) at (5.4,-3.55) {$\nu$};2416  \draw[fw] (mu2) -- (T3);2417  \draw[fw] (T3) -- (c2);2418  \draw[fw] (c2) |- (7.0,-2.25);2419  \draw[fw] (c2) |- (nu2);2420  \draw[fw] (nu2) -- (7.0,-3.55);