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 581–680 of 4249. Source text is displayed literally.
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 prepares609\cref{ch:cocycle}: the hypothesis that matters is a cocycle condition, and the others are regularity.610 611\section{Khinchin's theorem}612 613Let $H$ assign a real number to each $p\in\Delta_n$ for every $n\ge1$. We assume throughout that $H$ is614symmetric, that is, invariant under permutations of $p_1,\dots,p_n$; Khinchin does not state this, but it615is implicit in his treating $H$ as a function of the scheme. Consider the conditions:616\begin{enumerate}[label=(K\arabic*)]617\item for each $n$, $H$ is largest at the uniform distribution $u_n$;618\item for every joint distribution $r$ on $X\times Y$ with first marginal $p$,619$H(r)=H(p)+\sum_xp(x)H\bigl(r(\,\cdot\st x)\bigr)$;620\item $H(p_1,\dots,p_n,0)=H(p_1,\dots,p_n)$.621\end{enumerate}622 623\begin{theorem}[Khinchin]\label{thm:khinchin}624\Scl[\cite{Khi53}] If $H$ is continuous on each $\Delta_n$ and satisfies \textup{(K1)--(K3)}, then there is a625constant $\lambda\ge0$ with626\[ H(p)=-\lambda\sum_ip_i\log p_i. \]627\end{theorem}628 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}