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 2349–2448 of 4249. Source text is displayed literally.
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);2421\end{tikzpicture}2422\caption{The compound source and the proof that it is stationary. The shift slides through $\nu$ by2423equivariance and through the copy node because it is deterministic; it is then absorbed by $\mu$.}\label{fig:hookup}2424\end{figure}2425 2426\begin{theorem}[Khinchin]\label{thm:stationary}2427\Srf[\cite{Khi56}, \S10] If the source and the channel are stationary, so are the compound source and the output2428source.2429\end{theorem}2430 2431\begin{proof}2432$\cpy$ and $\nu$ are morphisms of $\Dyn$ and $\mu$ is a state, so $\omega$ is a state of $\Dyn$. Written out2433(\cref{fig:hookup}),2434\begin{align*}2435 (T\otimes T)\circ(\id\otimes\nu)\circ\cpy\circ\mu&=(\id\otimes\nu)\circ(T\otimes T)\circ\cpy\circ\mu\\2436 &=(\id\otimes\nu)\circ\cpy\circ T\circ\mu=\omega,2437\end{align*}2438using in turn the equivariance of $\nu$, the determinism of $T$, and the invariance of $\mu$.2439\end{proof}2440 2441The same reasoning shows that channels compose: from $[A,\nu,B]$ and $[B,\nu',C]$ one gets $[A,\nu'\circ\nu,C]$,2442stationary if both are. A stationary code is a deterministic channel, and coding a source before sending it2443through a channel is composition. Khinchin uses all of this in his last chapter, where a code is treated2444as a channel so that the previous theorems apply to it.2445 2446\section{Anticipation and naturality}2447 2448To see what absence of anticipation means, take one-sided time. The space $A^{\N}$ of sequences