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 321–420 of 4249. Source text is displayed literally.
321categorical 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.369 370\section{Schemes and their maps}371 372\begin{definition}\label{def:finprob}373A \term{finite probability space}, or finite scheme, is a pair $(X,p)$ of a finite set $X$ and a probability374distribution $p$ on it. A morphism $f\colon(X,p)\to(Y,q)$ is a map of sets with $f_*p=q$, that is,375$q(y)=\sum_{x\in f^{-1}(y)}p(x)$. These form the category $\FinProb$. The category $\FinStoch$ has finite376sets as objects and stochastic matrices as morphisms: a morphism $f\colon X\to Y$ is a family of377distributions $f(\,\cdot\st x)$ on $Y$, one for each $x\in X$, and378$(g\circ f)(z\st x)=\sum_yg(z\st y)f(y\st x)$.379\end{definition}380 381A distribution on $X$ is a morphism $1\to X$ in $\FinStoch$, a \term{state}. A map of sets is a stochastic382matrix with entries in $\{0,1\}$, so $\FinSet$ is a subcategory of $\FinStoch$, and a morphism of383$\FinProb$ is a map of sets that carries one state to another. We write $\Delta_n$ for the simplex of384distributions on $\{1,\dots,n\}$ and $u_n$ for the uniform one.385 386$\FinStoch$ is a symmetric monoidal category under the product of sets and the tensor product of387matrices, $(f\otimes g)(y,y'\st x,x')=f(y\st x)\,g(y'\st x')$. Each object has a copy map388$\cpy_X\colon X\to X\times X$ and a delete map $\del_X\colon X\to1$, both coming from $\FinSet$. These data389make it a \emph{Markov category} (\cref{app:toolkit}). A morphism $f$ is \term{deterministic} when it390commutes with copying, $\cpy_Y\circ f=(f\otimes f)\circ\cpy_X$; in $\FinStoch$ these are exactly the maps of391sets. A state is deterministic exactly when it is a point mass. We shall see in \cref{ch:inequalities} that392entropy measures by how much a state fails this equation.393 394Khinchin's product scheme $AB$ needs a comment. Given schemes $A$ and $B$ he considers the events $A_iB_k$395and their probabilities, which presupposes that $A$ and $B$ are defined on a common probability space. In396our terms there is a space $(\Omega,P)$ and two morphisms out of it,397\[ (X,p)\xleftarrow{\ a\ }(\Omega,P)\xrightarrow{\ b\ }(Y,q), \]398and $AB$ is the image of the pairing, a distribution $r$ on $X\times Y$ with marginals $p$ and $q$. It is the399product distribution $p\otimes q$ only when $A$ and $B$ are independent. \Cref{ch:cocycle} takes the common400space $\Omega$ as the basic datum.401 402\section{Entropy}403 404\begin{definition}\label{def:entropy}405The \term{entropy} of a distribution $p$ on a finite set $X$ is406\[ H(p)=-\sum_{x\in X}p(x)\log p(x), \]407with $0\log0=0$ and logarithms to base $2$.408\end{definition}409 410For a joint distribution $r$ on $X\times Y$ with marginals $p$ and $q$, write $r(\,\cdot\st x)$ for the411conditional distribution on $Y$ given $x$, defined when $p(x)>0$, and put412\[ H_A(B)=\sum_xp(x)\,H\bigl(r(\,\cdot\st x)\bigr). \]413This is Khinchin's conditional entropy of $B$ given $A$; the modern notation is $H(B\st A)$.414 415\begin{proposition}[Khinchin's properties]\label{prop:properties}416\Scl[\cite{Sha48,Khi53}]417\begin{enumerate}[label=(\roman*)]418\item $H(p)\ge0$, with equality iff $p$ is a point mass.419\item $H(p)\le\log|X|$, with equality iff $p$ is uniform.420\item $H(r)=H(p)+H_A(B)$.