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 1181–1280 of 4249. Source text is displayed literally.
1181\begin{theorem}[Data processing]\label{thm:DPI}1182\Scl For every kernel $f\colon X\to Y$ and states $p,p'$ on $X$,1183\[ \KL{f\circ p}{f\circ p'}\le\KL p{p'}. \]1184\end{theorem}1185 1186\begin{proof}1187Apply \cref{prop:chainD} to $r=p\rtimes f$ and $r'=p'\rtimes f$ in two ways. Conditioning on $X$, the conditional1188distributions agree, so $\KL r{r'}=\KL p{p'}$. Conditioning on $Y$,1189$\KL r{r'}=\KL{f\circ p}{f\circ p'}+\sum_y(f\circ p)(y)\,\KL{r(\,\cdot\st y)}{r'(\,\cdot\st y)}$, and the last sum is nonnegative by1190\cref{prop:gibbs}.1191\end{proof}1192 1193The proof shows what the inequality is made of. The chain rule is an identity, and we saw in1194\cref{ch:schemes} that for entropy it is functoriality. Positivity is an order relation. Data processing is1195the two together.1196 1197\section{Composition is short}1198 1199Relative entropy between states extends to parallel morphisms. For $f,g\colon X\to Y$ in $\FinStoch$ put1200\[ \KL fg=\max_{x\in X}\KL{f(\,\cdot\st x)}{g(\,\cdot\st x)}. \]1201 1202\begin{theorem}\label{thm:enriched}1203\Sli[\cite{Per24}] With this divergence on its hom-sets, $\FinStoch$ is a Markov category enriched in1204divergence spaces: for all composable morphisms,1205\begin{gather*}1206 \KL{h\circ f}{h\circ g}\le\KL fg,\qquad\KL{f\circ k}{g\circ k}\le\KL fg,\\1207 \KL{f\otimes f'}{g\otimes g'}=\KL fg+\KL{f'}{g'}.1208\end{gather*}1209\end{theorem}1210 1211\begin{proof}1212The first inequality is \cref{thm:DPI} applied to each input. The second follows from the joint convexity of1213relative entropy, since $(f\circ k)(\,\cdot\st w)$ is a mixture of the $f(\,\cdot\st x)$ with weights1214$k(x\st w)$. The third is additivity of relative entropy on product distributions.1215\end{proof}1216 1217A \term{divergence space} is a set with a function $D$ to $[0,\infty]$ vanishing on the diagonal; no symmetry1218or triangle inequality is asked. The theorem says that composition and tensoring are non-expansive maps of1219such spaces. The same holds for other divergences, for instance the R\'enyi divergences and the total1220variation distance $\TV(p,q)=\frac12\sum_x|p(x)-q(x)|$, which is a metric. This is the pattern announced at the1221end of \cref{ch:schemes}: an equation for deterministic morphisms, here $f\circ p=f\circ p'$ following1222from $p=p'$, has a quantitative form for all morphisms.1223 1224\section{Entropy as distance from determinism}1225 1226A state $p$ on $X$ is deterministic when $\cpy_X\circ p=p\otimes p$: drawing once and copying is the same as1227drawing twice. For a general state the two sides differ, and the difference can be measured.1228 1229\begin{proposition}\label{prop:copy}1230\Sli[\cite{Per24}] For a state $p$ on $X$ and a joint state $r$ on $X\times Y$ with marginals $p,q$,1231\[ H(p)=\KL{\cpy_X\circ p}{p\otimes p},\qquad I(X;Y)=\KL r{p\otimes q}. \]1232With total variation in place of relative entropy the first expression becomes $1-\sum_xp(x)^2$.1233\end{proposition}1234 1235\begin{proof}1236$\cpy_X\circ p$ is concentrated on the diagonal with weights $p(x)$, and1237$\sum_xp(x)\log\frac{p(x)}{p(x)^2}=H(p)$. The second formula is $\sum r\log r-\sum r\log p-\sum r\log q$. For the last1238statement, $\frac12\bigl[\sum_x(p(x)-p(x)^2)+\sum_{x\ne x'}p(x)p(x')\bigr]=1-\sum_xp(x)^2$.1239\end{proof}1240 1241So entropy is the mutual information of a variable with itself, and it is defined by the Markov category1242structure together with the divergence. The quantity $1-\sum_xp(x)^2$ is the Gini--Simpson index of1243ecology. Entropy and mutual information need no separate axiomatization once the enrichment is given; what1244needs a choice is the divergence.1245 1246\section{Shannon's inequality and its two generalizations}1247 1248By \cref{prop:copy,prop:gibbs}, $I(X;Y)\ge0$, which is Shannon's inequality $H_A(B)\le H(B)$.1249 1250Khinchin's first generalization is contained in the proof we gave of \cref{prop:properties}(iv). That proof1251applied Jensen's inequality for each value of the second variable separately, and therefore proves more1252than the summed statement.1253 1254\begin{lemma}[Khinchin's Lemma 1.1]\label{lem:partial}1255\Scl[\cite{Khi56}] Let $r$ be a joint distribution on $X\times Y$ with marginals $p,q$. For every subset1256$S\subseteq Y$,1257\[ -\sum_xp(x)\sum_{y\in S}r(y\st x)\log r(y\st x)\ \le\ -\sum_{y\in S}q(y)\log q(y). \]1258\end{lemma}1259 1260The second generalization is the conditional form.1261 1262\begin{lemma}[Khinchin's Lemma 1.2]\label{lem:SSA}1263\Scl[\cite{Khi56}] For three schemes, $H_{AB}(C)\le H_B(C)$. Equivalently, the \term{conditional mutual1264information} $I(A;C\st B)=H_B(C)-H_{AB}(C)$ is nonnegative.1265\end{lemma}1266 1267\begin{proof}1268$I(A;C\st B)=\sum_bP(b)\,I(A;C)_{P|_b}$, an average of mutual informations.1269\end{proof}1270 1271In the language of \cref{ch:cocycle} these inequalities are statements about the function $X\mapsto H[X](P)$1272on the monoid of observables, for a fixed law $P$. Recall that $XY$ is the join of $X$ and $Y$ in the1273refinement order; write $X\wedge Y$ for the meet, the finest observable refined by both.1274 1275\begin{proposition}\label{prop:submodular}1276\Scl[cf.\ \cite{Fuj78}] For every law $P$ the function $H[\,\cdot\,](P)$ on $\Pi(\Omega)$ is1277\begin{enumerate}[label=(\roman*)]1278\item monotone: $H[X]\ge H[Y]$ if $X$ refines $Y$;1279\item submodular: $H[XY]+H[X\wedge Y]\le H[X]+H[Y]$;1280\item and satisfies $H[XYZ]+H[Y]\le H[XY]+H[YZ]$ for all $X,Y,Z$.