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

709are 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: it781fixes the function up to a scalar. \Cref{ch:rates} returns to the R\'enyi family, which reappears when782coding is required to be exact.783 784Regularity cannot be dropped altogether. If $\ell\colon(0,1]\to\R$ satisfies $\ell(xy)=\ell(x)+\ell(y)$, then785$p\mapsto-\sum_ip_i\ell(p_i)$ satisfies the chain rule, by the same computation as for the logarithm. Using786the axiom of choice one can take $\ell=A\circ\log$ with $A$ a discontinuous additive function, and the result787is not a multiple of entropy. Measurability is enough to exclude this \cite{Lee64}.788 789\section*{Notes}790 791Shannon's axiomatic remark is in \cite[\S6]{Sha48}; Khinchin's theorem is \cite[\S2]{Khi53}. Faddeev's792theorem is \cite{Fad56}; R\'enyi \cite{Ren61} simplified the proof and introduced the entropies named793after him. The monograph of Acz\'el and Dar\'oczy \cite{AD75} surveys the functional-equation literature.794The functorial characterization is \cite{BFL11}; the operadic and categorical-algebra viewpoint is in795\cite{Lei21}, and the derivation viewpoint in \cite{Bra21}. Parzygnat \cite{Par22} gives a functorial796characterization of von Neumann entropy in the same spirit.797 798\section*{Exercises}799 800\begin{exercise}801Carry out the second step of Khinchin's proof for $p=(\tfrac12,\tfrac13,\tfrac16)$: describe the joint802distribution $r$, and verify numerically that $\log g-\sum_ip_i\log g_i=H(p)$.803\end{exercise}804 805\begin{exercise}\label{exer:recursive}806Show that symmetry and Faddeev's recursivity imply $H(p\circ_iq)=H(p)+p_iH(q)$ for all $q\in\Delta_k$, by807induction on $k$, and deduce the full chain rule.808\end{exercise}