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 229–328 of 4249. Source text is displayed literally.
229and seventy years on they are still a good place to learn what the theorems say.230 231They were written in the mathematical language available at the time, which was that of measures on232product spaces. This book rewrites them in a language that was not available. The claim is not that233category theory proves Shannon's theorems; for the most part it does not, and the places where it does not234are marked. The claim is that three features of Khinchin's text, each of which he states in words and then235handles by computation, are structure that can now be named.236 237The first is the additivity axiom $H(AB)=H(A)+H_A(B)$. It is the condition for a function on observables to be238a 1-cocycle for the action of observables on functions by conditioning, and the uniqueness theorem computes a239cohomology group: $H^1\iso\R$, generated by entropy (\cref{ch:cocycle}). Symmetry of entropy is then240not an axiom but the commutativity of a monoid; the Tsallis entropies are the coboundaries of a deformed241action; and Shannon entropy is what survives when the deformation is switched off.242 243The second is Khinchin's remark that ``formally every code can be regarded as a channel'', together with244his construction of the compound source. Sources, codes and channels are the states and the morphisms of one245category, that of shift-equivariant Markov kernels. The compound source is a composite, and his theorem246that it is stationary is the statement that composition preserves equivariance (\cref{ch:channels}). The247same category, taken up to almost sure equality, carries a dagger. Conditional expectations are its248idempotents, and the two limits in McMillan's theorem, over longer pasts and over longer times, are limits249of idempotents (\cref{ch:martingales,ch:aep}).250 251The third is the form of the two asymptotic theorems on which everything rests. McMillan's theorem says that252a long block from an ergodic source is, up to $\varepsilon$, a uniform choice among $2^{nH}$ sequences.253Feinstein's lemma says that a long block of channel uses is, up to $\varepsilon$, an identity map on254$2^{nC}$ messages. Both are statements about approximate retractions, entropy and capacity are the255corresponding ranks, and Shannon's theorem is that retractions compose (\cref{ch:feinstein,ch:shannon}).256What the tolerance $\varepsilon$ buys can be said exactly: without it a whole spectrum of invariants is257needed, and with it the spectrum collapses to a point (\cref{ch:rates}).258 259The reader will find that the amount of genuinely higher structure varies. The first part uses260homological algebra and operads in earnest. The second and third use monoidal, enriched and dagger261categories, which are low-dimensional. \Cref{ch:coda} says where we think the language earned its place and262where it only relabelled.263 264\chapter{Introduction}265 266\section*{What is assumed}267 268We assume basic category theory (functors, natural transformations, limits, adjunctions, monoidal269categories) and measure-theoretic probability at the level of a first graduate course. Markov categories,270operads, monoid cohomology, enrichment and dagger categories are introduced as needed and collected in271\cref{app:toolkit}. No information theory is assumed; every classical notion is defined, and every classical272theorem is either proved or cited.273 274Logarithms are to base $2$ unless written $\ln$, so entropies are in bits. We write $\hb(x)=-x\log x-(1-x)\log(1-x)$275for the binary entropy function and use the convention $0\log 0=0$.276 277\section*{How the book is organized}278 279\Cref{fig:intro} shows the one picture to keep in mind. A source is a state $\mu$, a channel is a morphism280$\nu$, codes are deterministic morphisms, and using a channel means composing with it. Everything in281Parts~II and III is about this diagram and its finite truncations.282 283\begin{figure}[ht]\centering284\begin{tikzpicture}[x=1cm,y=1cm]285 \node[ogbox] (mu) at (0,0) {$\mu$};286 \node[ogbox] (e) at (2.3,0) {$e$};287 \node[ogbox] (nu) at (4.6,0) {$\nu$};288 \node[ogbox] (d) at (6.9,0) {$d$};289 \draw[fw] (mu) -- node[above=2pt,lab,black]{$A_0^{\Z}$} (e);290 \draw[fw] (e) -- node[above=2pt,lab,black]{$\AZ$} (nu);291 \draw[fw] (nu) -- node[above=2pt,lab,black]{$\BZ$} (d);292 \draw[fw] (d) -- node[above=2pt,lab,black]{$A_0^{\Z}$} (9.0,0);293\end{tikzpicture}294\caption{A source $\mu$, an encoder $e$, a channel $\nu$ and a decoder $d$. Each box is a shift-equivariant295Markov kernel; the encoder and decoder are deterministic. Shannon's theorem asks when the composite296$d\circ\nu\circ e$ can be made close to the identity on $\mu$-typical inputs.}\label{fig:intro}297\end{figure}298 299\textbf{Part~I} is about entropy as a function. \Cref{ch:schemes} sets up finite schemes as a category and300shows that conditional entropy is the entropy of a morphism, so that the chain rule is functoriality.301\Cref{ch:uniqueness} proves Khinchin's uniqueness theorem and places it among its successors: Faddeev's302theorem, the functorial characterization of Baez, Fritz and Leinster, and the operadic one. \Cref{ch:cocycle}303develops information cohomology in a finite and explicit form. \Cref{ch:inequalities} treats Khinchin's304elementary inequalities through relative entropy and the data-processing inequality, which is the statement305that composition is short for a divergence.306 307\textbf{Part~II} is about sources. \Cref{ch:sources} constructs sequence spaces as infinite tensor products,308defines the entropy rate, and reads finite-state sources as coalgebras. \Cref{ch:ergodic} treats ergodicity309and the ergodic decomposition. \Cref{ch:martingales} is about conditional expectations as idempotents and310the convergence of martingales. \Cref{ch:aep} proves McMillan's theorem in mean from two soft convergence311statements and one elementary estimate.312 313\textbf{Part~III} is about channels. \Cref{ch:channels} defines channels with memory, repairs a gap in314Khinchin's treatment of ergodicity that was found soon after publication, and studies capacity as a315function on a monoidal category. \Cref{ch:feinstein} proves Feinstein's lemma in its one-shot form and316reads codes as approximate retractions. \Cref{ch:shannon} proves the coding theorems and their converses, and317shows the martingale returning as the engine of an explicit construction. \Cref{ch:rates} places entropy and318capacity among asymptotic invariants of preordered semirings.319 320\textbf{Part~IV}, \cref{ch:coda}, is an assessment and a list of open problems. The appendices contain the321categorical toolkit, a concordance with Khinchin's text, a description of the computational checks, and322solutions to all exercises.323 324\section*{A dictionary}325 326\begin{center}\small327\renewcommand{\arraystretch}{1.25}328\begin{tabular}{@{}p{0.40\textwidth}p{0.52\textwidth}@{}}