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 509–608 of 4249. Source text is displayed literally.
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}601%% ---- end ch/01-schemes.tex ----602%% ---- begin ch/02-uniqueness.tex ----603\chapter{The Uniqueness Theorem}\label{ch:uniqueness}604 605Shannon remarked that his formula for entropy is forced by a few natural requirements, and gave an argument.606Khinchin's first paper turned the remark into a theorem with a complete proof, and Faddeev sharpened it607three years later. The result has been reproved and reformulated many times since. This chapter proves608Khinchin's version, states its main descendants, and asks which hypothesis does what. The answer prepares