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 389–488 of 4249. Source text is displayed literally.
389make 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)$.421\item $H_A(B)\le H(q)$, with equality iff $r=p\otimes q$. In particular $H(p\otimes q)=H(p)+H(q)$.422\end{enumerate}423\end{proposition}424 425\begin{proof}426Let $\varphi(t)=-t\log t$, a strictly concave function on $[0,1]$ vanishing at $0$ and $1$. (i) is clear.427(ii) By Jensen's inequality $\frac1n\sum_x\varphi(p(x))\le\varphi(\frac1n)$ with $n=|X|$. (iii) Write428$r(x,y)=p(x)\,r(y\st x)$ and take logarithms. (iv) Since $q(y)=\sum_xp(x)\,r(y\st x)$, Jensen's inequality gives429$\varphi(q(y))\ge\sum_xp(x)\,\varphi(r(y\st x))$ for each $y$; sum over $y$. Equality requires $r(y\st x)$ to be430independent of $x$.431\end{proof}432 433\begin{example}\label{ex:first}434For $p=(\tfrac12,\tfrac14,\tfrac18,\tfrac18)$ we have $H(p)=\tfrac12\cdot1+\tfrac14\cdot2+2\cdot\tfrac18\cdot3=1.75$ bits. A435uniform distribution on four points has $2$ bits. One can identify an outcome of $p$ by asking ``is it the436first?'', then ``is it the second?'', then ``is it the third?'', which takes $1$, $2$, $3$ or $3$437questions and $1.75$ on average.438\end{example}439 440\section{The entropy of a map}441 442Property (iii) is usually read as a rule for computing the entropy of a joint distribution. Read in443the other direction, it says what a difference of entropies is.444 445\begin{definition}\label{def:Hmap}446Let $f\colon(X,p)\to(Y,q)$ be a morphism of $\FinProb$. For $y$ with $q(y)>0$ let $p_y$ be $p$ conditioned on447the fibre $f^{-1}(y)$. The \term{entropy of $f$} is448\[ H(f)=\sum_yq(y)\,H(p_y). \]449\end{definition}450 451\begin{proposition}\label{prop:loss}452\Scl[the chain rule] $H(f)=H(p)-H(q)$.453\end{proposition}454 455\begin{proof}456For $x$ in the fibre over $y$ we have $p(x)=q(y)\,p_y(x)$, so457$-\sum_xp(x)\log p(x)=-\sum_yq(y)\log q(y)-\sum_yq(y)\sum_{x\in f^{-1}y}p_y(x)\log p_y(x)$.458\end{proof}459 460\begin{theorem}[Entropy is a functor]\label{thm:functor}461\Sli[\cite{BFL11}] Regard the additive monoid $[0,\infty)$ as a category with one object. Then $f\mapsto H(f)$462is a functor $\FinProb\to[0,\infty)$:463\[ H(g\circ f)=H(f)+H(g),\qquad H(\id)=0. \]464Moreover $H(f)=0$ iff $f$ is injective on the support of $p$.465\end{theorem}466 467\begin{proof}468By \cref{prop:loss} the sum telescopes. $H(f)=0$ iff each $p_y$ is a point mass.469\end{proof}470 471The entropy of an object is recovered as the entropy of its unique map to the one-point space,472$H(p)=H\bigl((X,p)\to1\bigr)$, and Khinchin's conditional entropy as the entropy of a projection,473$H_A(B)=H\bigl(\pi_X\colon(X\times Y,r)\to(X,p)\bigr)$. Property (iii) is then functoriality along474\[ (X\times Y,r)\xrightarrow{\ \pi_X\ }(X,p)\longrightarrow1. \]475So the statement Khinchin singles out as the essential property of entropy says that entropy is a functor,476and the definition of conditional entropy as an average over fibres says what that functor does to a map477that is not a projection to a point. $H(f)$ is the information lost by applying $f$; equivalently, it is the478average information needed to recover $x$ from $f(x)$.479 480\begin{example}\label{ex:coarse}481Let $p$ be as in \cref{ex:first}. The map $f$ that merges the last two outcomes has image482$q=(\tfrac12,\tfrac14,\tfrac14)$ with $H(q)=1.5$, so $H(f)=0.25$. Directly: only the fibre over the third483point is not a singleton, it has probability $\tfrac14$ and conditional distribution $(\tfrac12,\tfrac12)$, so484$H(f)=\tfrac14\cdot1$. The map $f'$ that merges the first two outcomes has $H(f')=\tfrac34\,\hb(\tfrac23)\approx0.689$.485Merging likely outcomes loses more.486\end{example}487 488\section{Mixtures and the operad of simplices}