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 629–728 of 4249. Source text is displayed literally.
629Khinchin says that $\lambda$ is positive. The zero function satisfies the hypotheses, so $\lambda=0$ must be630allowed.631 632\begin{lemma}\label{lem:monotone}633\Scl Let $L\colon\{1,2,\dots\}\to\R$ be nondecreasing with $L(mn)=L(m)+L(n)$. Then $L(n)=\lambda\log n$ with634$\lambda=L(2)\ge0$.635\end{lemma}636 637\begin{proof}638$L(1)=0$, so $L\ge0$. Fix $n\ge2$ and $k\ge1$ and choose $m$ with $2^m\le n^k<2^{m+1}$. Monotonicity and639additivity give $mL(2)\le kL(n)\le(m+1)L(2)$, and also $m\le k\log n<m+1$. If $L(2)=0$ then $L(n)=0$. Otherwise640$|L(n)/L(2)-\log n|\le1/k$ for every $k$.641\end{proof}642 643\begin{proof}[Proof of \cref{thm:khinchin}]644Put $L(n)=H(u_n)$. By (K3) and (K1), $L(n)=H(\tfrac1n,\dots,\tfrac1n,0)\le L(n+1)$. Apply (K2) to the product of645$u_m$ and $u_n$: every conditional distribution is $u_n$, so $L(mn)=L(m)+L(n)$. By \cref{lem:monotone},646$L(n)=\lambda\log n$.647 648Now let $p$ have rational entries $p_i=g_i/g$ with positive integers $g_i$ summing to $g$. Let $Y$ be a set649of $g$ points divided into blocks of sizes $g_1,\dots,g_n$, and let $r$ be the joint distribution on650$\{1,\dots,n\}\times Y$ under which $i$ has distribution $p$ and, given $i$, the second coordinate is651uniform on the $i$-th block. Then $r$ is uniform on $g$ pairs and zero elsewhere, so $H(r)=L(g)$ by (K3)652and symmetry. Each conditional distribution is uniform on $g_i$ points, so (K2) reads653$L(g)=H(p)+\sum_ip_iL(g_i)$, that is,654\[ H(p)=\lambda\sum_ip_i(\log g-\log g_i)=-\lambda\sum_ip_i\log p_i. \]655Rational points with positive entries are dense in $\Delta_n$ and $H$ is continuous.656\end{proof}657 658The proof has two steps of different character. The second, which passes from uniform distributions to all659rational ones, uses only (K2) and (K3) and is pure algebra. The first, which determines $L$, is where a660regularity hypothesis is needed, and (K1) is used there and nowhere else. It supplies the monotonicity661that makes \cref{lem:monotone} a three-line argument.662 663\section{Faddeev's theorem and the operadic form}664 665Faddeev showed that (K1) can be dropped and (K2) weakened to its simplest instance.666 667\begin{theorem}[Faddeev]\label{thm:faddeev}668\Scl[\cite{Fad56}] Let $H$ be symmetric, with $H(t,1-t)$ continuous in $t$, and suppose that whenever669$p_n=q_1+q_2>0$,670\[ H(p_1,\dots,p_{n-1},q_1,q_2)=H(p_1,\dots,p_n)+p_n\,H\Bigl(\frac{q_1}{p_n},\frac{q_2}{p_n}\Bigr). \]671Then $H(p)=-\lambda\sum_ip_i\log p_i$ for a real constant $\lambda$.672\end{theorem}673 674The displayed condition is called recursivity. By induction it implies the chain rule of675\cref{prop:chainrule} in full (\cref{exer:recursive}), and expansibility (K3) follows by taking $q_2=0$. The676price of dropping (K1) is that $L(n)=H(u_n)$ is no longer known to be monotone. Faddeev replaces677\cref{lem:monotone} by a harder statement about additive arithmetic functions, in the spirit of a theorem678of Erd\H{o}s \cite{Erd46}:679 680\begin{lemma}\label{lem:faddeev}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 a