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

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}489 490For $q\in\Delta_m$ and $p_i\in\Delta_{k_i}$, $i=1,\dots,m$, define the composite491\[ q\circ(p_1,\dots,p_m)=(q_1p_{11},\dots,q_1p_{1k_1},\ \dots,\ q_mp_{m1},\dots,q_mp_{mk_m})\in\Delta_{k_1+\dots+k_m}. \]492This is the distribution of a two-stage experiment: choose $i$ according to $q$, then an outcome according493to $p_i$. Composition is associative and has the unit $u_1\in\Delta_1$, and permuting the entries of $q$494permutes blocks. The simplices therefore form a symmetric topological operad $\Delta=(\Delta_n)_{n\ge1}$495(\cref{app:toolkit}).496 497\begin{proposition}[Chain rule, operadic form]\label{prop:chainrule}498\Scl $H\bigl(q\circ(p_1,\dots,p_m)\bigr)=H(q)+\sum_{i=1}^mq_i\,H(p_i)$.499\end{proposition}500 501\begin{proof}502The composite is a distribution $p$ on a set mapping to $\{1,\dots,m\}$ with image $q$ and conditional503distributions $p_i$ on the fibres. Apply \cref{prop:loss}.504\end{proof}505 506Conversely every morphism $f\colon(X,p)\to(Y,q)$ exhibits $p$ as a composite $q\circ(p_y)_{y\in Y}$, up to the507order of the points. Morphisms of $\FinProb$ are operadic composites, and $H(f)=\sum_yq(y)H(p_y)$ is the second508term of the chain rule.509 510There is a second structure. For $\lambda\in[0,1]$ and two objects, let511$\lambda(X,p)\oplus(1-\lambda)(X',p')$ be the disjoint union $X\sqcup X'$ with the distribution512$\lambda p$ on $X$ and $(1-\lambda)p'$ on $X'$. The same formula on maps defines513$\lambda f\oplus(1-\lambda)f'$.514 515\begin{proposition}\label{prop:convexlinear}516\Sli[\cite{BFL11}] $H$ is convex-linear on morphisms:517\[ H\bigl(\lambda f\oplus(1-\lambda)f'\bigr)=\lambda H(f)+(1-\lambda)H(f'). \]518On objects, $H\bigl(\lambda p\oplus(1-\lambda)p'\bigr)=\lambda H(p)+(1-\lambda)H(p')+\hb(\lambda)$.519\end{proposition}520 521\begin{proof}522A fibre of $\lambda f\oplus(1-\lambda)f'$ is a fibre of $f$ or of $f'$, with the same conditional distribution523and with weight multiplied by $\lambda$ or $1-\lambda$. The second formula is \cref{prop:chainrule} for524$(\lambda,1-\lambda)\circ(p,p')$.525\end{proof}526 527The two statements do not conflict. The entropy of an object is the entropy of its map to $1$, and the528mixture of the maps $(X,p)\to1$ and $(X',p')\to1$ is a map to the two-point space with distribution529$(\lambda,1-\lambda)$, not to $1$. The term $\hb(\lambda)$ is the entropy of the remaining map to $1$. A530function on objects that is not affine comes from a function on morphisms that is.531 532\section{Kernels, noise and equivocation}533 534Let $f\colon X\to Y$ be a morphism of $\FinStoch$ and $p$ a state on $X$. The joint distribution535$r(x,y)=p(x)f(y\st x)$ on $X\times Y$ has marginals $p$ and $q=f\circ p$. Its two conditional entropies have536names:537\begin{align*}538 H(Y\st X)&=\sum_xp(x)\,H\bigl(f(\,\cdot\st x)\bigr)&&\text{(noise)},\\539 H(X\st Y)&=H(\pi_Y)&&\text{(equivocation)}.540\end{align*}541The \term{mutual information} is $I(X;Y)=H(p)+H(q)-H(r)=H(q)-H(Y\st X)=H(p)-H(X\st Y)$. By542\cref{prop:properties}(iv) it is nonnegative and vanishes iff $r=p\otimes q$.543 544When $q$ has full support there is a unique kernel $f^\dagger\colon Y\to X$ with545\[ p(x)\,f(y\st x)=q(y)\,f^\dagger(x\st y), \]546the \term{Bayesian inverse} of $f$ with respect to $p$. Noise and equivocation are exchanged by547$f\mapsto f^\dagger$. If $f$ is a map of sets its noise is zero and its Bayesian inverse is548$f^\dagger(\,\cdot\st y)=p_y$, so that549\[ H(f)=\sum_yq(y)\,H\bigl(f^\dagger(\,\cdot\st y)\bigr). \]550 551\begin{proposition}\label{prop:lossnoise}552\Srf[\cite{BF14,FuP21}] The entropy of a morphism of $\FinProb$ is the noise of its Bayesian inverse. For a553general kernel $f$ and state $p$,554\[ H(X\st Y)=H(p)-H(q)+H(Y\st X). \]555\end{proposition}556 557So the functor of \cref{thm:functor} is the restriction to deterministic maps of the equivocation, which is558defined for all kernels. The equivocation is not additive under composition of kernels, only subadditive559(\cref{exer:triangle}); it becomes additive on maps because their noise is zero. This is the first560appearance of a pattern that will recur. A statement that is an equality for deterministic morphisms