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 1089–1188 of 4249. Source text is displayed literally.
1089\begin{theorem}\label{thm:topos}1090\Sli[\cite{Vig20}] Information cohomology is $\Ext^\bullet_{\mathcal{A}}(\R,\Fun)$, computed in the abelian1091category of $\mathcal{A}$-modules in the topos of presheaves on $\Sinf$. A relative bar resolution of the1092trivial module $\R$ yields the complex of \cref{def:complex}. If every observable in $\Sinf$ can be written1093as a product of two others in a nondegenerate way, $H^1$ is a product of copies of $\R$, one for each1094connected component of $\Sinf$, each generated by a multiple of entropy.1095\end{theorem}1096 1097The generality matters when not all observables are jointly measurable, as in quantum theory or in the1098contextual situations studied by sheaf-theoretic methods. For our purposes the finite full structure is1099enough.1100 1101About degrees above one much less is known. If the conditioning action is replaced by the trivial action,1102the coboundary of entropy is $H[Y]+H[Z]-H[YZ]$, the mutual information, and the higher alternating sums are1103the multivariate mutual informations \cite{BB15}; these fit together into Hu's theorem that entropy1104extends to a signed measure on the Boolean algebra generated by the observables \cite{Hu62,Yeu08}. For the1105conditioning action itself we know of no general computation of $H^n(\Omega)$ for $n\ge2$.1106 1107\section*{Notes}1108 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$,