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 1109–1208 of 4249. Source text is displayed literally.
1109Information cohomology was introduced by Baudot and Bennequin \cite{BB15}; the topos-theoretic foundations,1110the bar resolution, and the treatment of the Tsallis case are due to Vigneaux \cite{Vig20,Vig19}, who also1111treats Gaussian laws, where differential entropy and the dimension appear as cocycles. The fundamental1112equation has a long history, for which see \cite{AD75}; its generalization of degree $\alpha$ is due to1113Dar\'oczy \cite{Dar70}, and the entropies $S_\alpha$ to Havrda and Charv\'at \cite{HC67} and Tsallis1114\cite{Tsa88}. Cathelineau \cite{Cat88} met the equation in the homology of $\mathrm{SL}_2$, which is the1115origin of the connection with polylogarithms pursued in \cite{Kon95,EVG02}. Entropy modulo a prime is1116developed by Leinster \cite{Lei21p}.1117 1118\section*{Exercises}1119 1120\begin{exercise}1121Show that $Y._\alpha(Z._\alpha f)=(YZ)._\alpha f$ for every $\alpha>0$, and that the constant function $1$ is1122invariant under the $\alpha$-action iff $\alpha=1$.1123\end{exercise}1124 1125\begin{exercise}1126Verify directly that $S_\alpha[YZ]=S_\alpha[Y]+Y._\alpha S_\alpha[Z]$. For independent $Y$ and $Z$ deduce1127$S_\alpha[YZ]=S_\alpha[Y]+S_\alpha[Z]-(\alpha-1)S_\alpha[Y]S_\alpha[Z]$.1128\end{exercise}1129 1130\begin{exercise}\label{exer:two}1131Let $|\Omega|=2$. Describe all 1-cocycles and compute $H^1(\Omega)$.1132\end{exercise}1133 1134\begin{exercise}1135Show that $h(x)=x$ satisfies \eqref{eq:FEITH}, and that $\hb$ satisfies it by computing $H(x,y,1-x-y)$ in two1136ways. Why does $h(x)=x$ not contradict \cref{thm:H1}?1137\end{exercise}1138 1139\begin{exercise}1140Prove the congruence $\partial_p(ab)\equiv a\,\partial_p(b)+\partial_p(a)\,b\pmod p$. Compute $H_5(2,4)$ from the1141definition 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*}