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

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}589 590\begin{exercise}\label{exer:doubly}591Let $W$ be a stochastic matrix from a finite set $X$ to itself. Show that $H(W\circ p)\ge H(p)$ for every592state $p$ if and only if $W$ is doubly stochastic. (For the direct implication you may use that a doubly593stochastic matrix is a convex combination of permutation matrices.)594\end{exercise}595 596\begin{exercise}\label{exer:triangle}597Let $X\to Y\to Z$ be composable kernels with a state on $X$. Show that598$H(X\st Z)\le H(X\st Y)+H(Y\st Z)$, with equality when both kernels are deterministic. Give an example of599strict inequality.600\end{exercise}