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

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 morphisms561weakens to an inequality for stochastic ones, and the inequality is the useful part.562 563\section*{Notes}564 565Entropy and its properties are due to Shannon \cite{Sha48}; Khinchin's account is \cite[\S1]{Khi53}. Categories566of probability spaces and stochastic maps go back to Lawvere \cite{Law62}, \v{C}encov \cite{Cen82} and Giry567\cite{Gir82}. Markov categories were introduced by Cho and Jacobs \cite{CJ19} and Fritz \cite{Fri20}. The568observation that entropy is naturally a function of a morphism, and \cref{thm:functor}, are due to Baez,569Fritz and Leinster \cite{BFL11}; the operad of simplices and its role are developed in Leinster's book570\cite{Lei21}. The extension of the information-loss functor to stochastic maps is studied by Fullwood and571Parzygnat \cite{FuP21}.572 573\section*{Exercises}574 575\begin{exercise}576For $p=(\tfrac12,\tfrac14,\tfrac18,\tfrac18)$, let $g$ merge the first two outcomes and then $h$ merge the577two remaining light outcomes. Compute $H(g)$, $H(h)$ and $H(h\circ g)$, and check \cref{thm:functor}.578\end{exercise}579 580\begin{exercise}581Show that $H(f)=H(p)$ iff $f_*p$ is a point mass, and that isomorphic objects of $\FinProb$ have the same582entropy. Is the converse true?583\end{exercise}584 585\begin{exercise}\label{exer:grouping}586Let $p\in\Delta_n$ with $p_1=t$. Show that $H(p)\le\hb(t)+(1-t)\log(n-1)$, with equality iff the remaining587mass is spread uniformly.588\end{exercise}