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 681–780 of 4249. Source text is displayed literally.
681\Scl[\cite{Fad56,Ren61}] If $a(mn)=a(m)+a(n)$ for all $m,n\ge1$ and $a(n+1)-\frac{n}{n+1}a(n)\to0$, then682$a(n)=c\log n$.683\end{lemma}684 685In the operadic language of \cref{ch:schemes} the theorem takes its cleanest form. Symmetry need not be686assumed.687 688\begin{theorem}[Faddeev--Leinster]\label{thm:FL}689\Sli[\cite{Lei21}, Thm.~2.5.1] Let $I=(I_n\colon\Delta_n\to\R)_{n\ge1}$ be a sequence of functions. The690following are equivalent:691\begin{enumerate}[label=(\roman*)]692\item each $I_n$ is continuous and $I\bigl(q\circ(p_1,\dots,p_m)\bigr)=I(q)+\sum_iq_iI(p_i)$ for all composable693$q,p_1,\dots,p_m$;694\item $I=cH$ for some $c\in\R$.695\end{enumerate}696\end{theorem}697 698\begin{proof}[Proof sketch]699Assume (i). From $u_1\circ(u_1)=u_1$ we get $I(u_1)=0$. From700$(1,0)\circ\bigl((1,0),u_1\bigr)=(1,0,0)=(1,0)\circ\bigl(u_1,(1,0)\bigr)$ we get $I(1,0)+I(1,0)=I(1,0)$, so701$I(1,0)=0$. Since $u_m\circ(u_n,\dots,u_n)=u_{mn}$, the sequence $a(n)=I(u_n)$ is additive. Since702$u_{n+1}=(\tfrac{n}{n+1},\tfrac1{n+1})\circ(u_n,u_1)$,703\[ a(n+1)-\tfrac{n}{n+1}\,a(n)=I\bigl(\tfrac{n}{n+1},\tfrac1{n+1}\bigr)\longrightarrow I(1,0)=0 \]704by continuity. \Cref{lem:faddeev} gives $a(n)=c\log n$. For rational $p$ with $p_i=g_i/g$ we have705$p\circ(u_{g_1},\dots,u_{g_n})=u_g$, so $I(p)=a(g)-\sum_ip_ia(g_i)=cH(p)$, and continuity finishes the proof.706\end{proof}707 708The identity $p\circ(u_{g_1},\dots,u_{g_n})=u_g$ is Khinchin's auxiliary scheme $B$. His proof and this one709are the same after the determination of $L$.710 711\section{The functorial characterization}712 713\Cref{thm:functor,prop:convexlinear} say that entropy is a convex-linear functor. Baez, Fritz and Leinster714showed that this characterizes it. Call a functor $F\colon\FinProb\to[0,\infty)$ \term{continuous} if715$F(f_k)\to F(f)$ whenever $f_k\colon(X,p_k)\to(Y,q_k)$ have the same underlying map as $f\colon(X,p)\to(Y,q)$716and $p_k\to p$.717 718\begin{theorem}[Baez--Fritz--Leinster]\label{thm:BFL}719\Sli[\cite{BFL11}] Let $F\colon\FinProb\to[0,\infty)$ be a functor that is convex-linear and continuous. Then720there is a constant $c\ge0$ such that for every $f\colon(X,p)\to(Y,q)$,721\[ F(f)=c\,\bigl(H(p)-H(q)\bigr). \]722\end{theorem}723 724\begin{proof}725For an object $(X,p)$ let $I(p)=F\bigl((X,p)\to1\bigr)$. Functoriality along $(X,p)\to(Y,q)\to1$ gives726$F(f)=I(p)-I(q)$. An isomorphism $\phi$ has $F(\phi)+F(\phi^{-1})=0$ with both terms nonnegative, so $I$ is727invariant under relabelling. Now let $p=q\circ(p_1,\dots,p_m)$ and let $f$ be the corresponding map to728$(\{1,\dots,m\},q)$. It is the convex combination, with weights $q_i$, of the maps from the $i$-th block to a729point, so convex-linearity gives $F(f)=\sum_iq_iI(p_i)$. Hence $I(p)=I(q)+\sum_iq_iI(p_i)$. $I$ is730continuous, so $I=cH$ by \cref{thm:FL}, and $c\ge0$ because $F\ge0$.731\end{proof}732 733Three things have changed relative to Khinchin's formulation. Nothing is assumed about maxima.734Symmetry is not an axiom; it is the fact that functors send isomorphisms to invertible elements. And735expansibility has disappeared, because adjoining an outcome of probability zero is an isomorphism in736$\FinProb$ once morphisms are taken up to null sets, or else follows from the chain rule as in737\cref{thm:faddeev}. What remains is the chain rule in two halves, functoriality and convex-linearity, and738continuity.739 740\section{Entropy as a derivation}741 742There is one more way to write the chain rule. For $p\in\Delta_n$, $q\in\Delta_k$ and $1\le i\le n$ let743$p\circ_iq\in\Delta_{n+k-1}$ be the result of replacing the $i$-th outcome of $p$ by a copy of $q$ scaled by744$p_i$. The full composite is an iterated partial composite, and the chain rule is equivalent to745\begin{equation}\label{eq:leibniz}746 H(p\circ_iq)=H(p)+p_i\,H(q).747\end{equation}748Let the operad $\Delta$ act on $\R$ on the left by $p\cdot_ir=p_ir$ and on the right trivially. Then749\eqref{eq:leibniz} is the Leibniz rule $d(p\circ_iq)=dp\cdot q+p\cdot_i dq$.750 751\begin{theorem}\label{thm:derivation}752\Sli[\cite{Bra21,Lei21}] Entropy is a derivation of the operad of simplices with values in $\R$, and every753continuous derivation is a real multiple of it.754\end{theorem}755 756The first statement is due to Bradley, who also gives a pointwise form of the converse; the second as757stated here is \cref{thm:FL}. Leinster proves a categorified version: $\FinProb$ is the free categorical758algebra for $\Delta$ containing an internal algebra, and the internal algebras in the one-object category759$(\R,+)$ are the multiples of entropy \cite[Ch.~12]{Lei21}, from which \cref{thm:BFL} follows.760 761A derivation is a 1-cocycle in Hochschild cohomology, and one expects a cohomology theory in which entropy762is a class. The next chapter constructs it, for a monoid in place of the operad.763 764\section{What the chain rule excludes}765 766How much of the theorem is due to the conditional form of (K2)? For $\alpha>0$, $\alpha\ne1$, the767\term{R\'enyi entropy} of order $\alpha$ is768\[ H_\alpha(p)=\frac{1}{1-\alpha}\log\sum_ip_i^\alpha. \]769It is continuous and symmetric, it satisfies (K1) and (K3), and it is additive on independent products,770$H_\alpha(p\otimes q)=H_\alpha(p)+H_\alpha(q)$. As $\alpha\to1$ it tends to $H(p)$; as $\alpha\to0$ it tends to771the \term{Hartley entropy} $\log|\supp p|$, and as $\alpha\to\infty$ to the min-entropy $-\log\max_ip_i$.772 773\begin{example}\label{ex:renyi}774Take $p=(\tfrac12,\tfrac14,\tfrac14)=(\tfrac12,\tfrac12)\circ(u_1,u_2)$. Then775$H_2(p)=-\log(\tfrac14+\tfrac1{16}+\tfrac1{16})=\log\tfrac83\approx1.415$, while the chain rule would predict776$H_2(\tfrac12,\tfrac12)+\tfrac12H_2(u_2)=1.5$.777\end{example}778 779So among Khinchin's hypotheses, everything except the conditional additivity (K2) for dependent schemes is780satisfied by a one-parameter family. The chain rule is the hypothesis with content, and it is strong: it