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

269categories) 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}@{}}329\toprule330\textbf{Khinchin} & \textbf{Here}\\\midrule331finite scheme & object of $\FinProb$; state $1\to X$ in $\FinStoch$\\332conditional entropy $H_A(B)$ & entropy of the projection $(A\times B,r)\to(A,p)$\\333$H(AB)=H(A)+H_A(B)$ & functoriality; the 1-cocycle condition\\334uniqueness theorem & $H^1\iso\R$; initiality of $\FinProb$\\335Shannon's inequality and its generalizations & positivity of relative entropy; submodularity\\336source $[A,\mu]$ & shift-invariant state on a Kolmogorov product\\337ergodic source & invariant state that is deterministic on the invariant $\sigma$-algebra\\338conditional probability given the past & dagger-split idempotent\\339the $E$ property & the block $A^n$ is an $\varepsilon$-retract of a set of $2^{nH}$ points\\340channel $[A,\nu_x,B]$ & equivariant Markov kernel $\AZ\to\BZ$\\341without anticipation & natural transformation of towers\\342connection of channel to source & composition after copying\\343distinguishable group of sequences & $\varepsilon$-retraction of the channel onto a finite set\\344ergodic capacity & asymptotic $\varepsilon$-rank\\345a code is a channel & deterministic morphisms are morphisms\\346\bottomrule347\end{tabular}348\end{center}349 350\section*{How to read the tags}351 352A reader who wants only the mathematics of information theory can read the statements tagged353\textsf{classical} and their proofs; they are complete in themselves. A reader who knows that mathematics354and wants the categorical account can read the statements tagged \textsf{literature} and355\textsf{reformulation}. The tags \textsf{observation} and \textsf{programme} mark where we are on our own:356the first for elementary remarks with proofs, the second for directions without them.357%% ---- end front.tex ----358\mainmatter359\part{Entropy}360%% ---- begin ch/01-schemes.tex ----361\chapter{Finite Schemes}\label{ch:schemes}362 363Khinchin's first paper begins with a \emph{finite scheme}: a complete system of mutually exclusive events364$A_1,\dots,A_n$ together with their probabilities $p_1,\dots,p_n$. He defines its entropy, lists the properties365of entropy that will be needed later, and observes that one of them, the rule for the entropy of a product366scheme, is the important one. This chapter does the same, with one change of emphasis. Finite schemes form367a category, and the important property says that entropy is a functor on it. The entropy of a scheme is the368value of that functor on a particular map.