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

1141definition and from the truncated logarithm. Compute $H_3(2,2)$ and $H_3(1,1,2)$, and check the chain rule for1142$(1,1,2)=(2,2)\circ\bigl((2,2),(1)\bigr)$ in $\mathbb{F}_3$.1143\end{exercise}1144%% ---- end ch/03-cocycle.tex ----1145%% ---- begin ch/04-inequalities.tex ----1146\chapter{Divergence and the Elementary Inequalities}\label{ch:inequalities}1147 1148Khinchin's second paper opens with a chapter of inequalities: two generalizations of Shannon's inequality1149$H_A(B)\le H(B)$ and three lemmas taken from Feinstein. They are the working tools of the later chapters.1150All of them follow from one fact, the positivity of relative entropy, together with the chain rule; and the1151form in which they are used, the data-processing inequality, says that composition of Markov kernels is1152non-expansive for a divergence. That statement is an enrichment of the category $\FinStoch$, and this1153chapter is organized around it.1154 1155\section{Relative entropy}1156 1157\begin{definition}1158For distributions $p,q$ on a finite set $X$, the \term{relative entropy}, or Kullback--Leibler divergence,1159is1160\[ \KL pq=\sum_xp(x)\log\frac{p(x)}{q(x)}, \]1161with the conventions $0\log\frac0q=0$ and $\KL pq=\infty$ if $p(x)>0=q(x)$ for some $x$.1162\end{definition}1163 1164\begin{proposition}[Gibbs' inequality]\label{prop:gibbs}1165\Scl $\KL pq\ge0$, with equality iff $p=q$.1166\end{proposition}1167 1168\begin{proof}1169$\ln t\le t-1$ with equality only at $t=1$, so $-\sum_xp(x)\ln\frac{q(x)}{p(x)}\ge\sum_x(p(x)-q(x))\ge0$, the sums being1170over the support of $p$.1171\end{proof}1172 1173For a state $p$ on $X$ and a kernel $f\colon X\to Y$ write $p\rtimes f$ for the joint distribution1174$p(x)f(y\st x)$ on $X\times Y$.1175 1176\begin{proposition}[Chain rule for relative entropy]\label{prop:chainD}1177\Scl For joint distributions $r,r'$ on $X\times Y$ with first marginals $p,p'$,1178\[ \KL r{r'}=\KL p{p'}+\sum_xp(x)\,\KL{r(\,\cdot\st x)}{r'(\,\cdot\st x)}. \]1179\end{proposition}1180 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