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 1229–1328 of 4249. Source text is displayed literally.
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$.1281\end{enumerate}1282\end{proposition}1283 1284\begin{proof}1285(i) is \cref{thm:functor}. (iii) is \cref{lem:SSA}, since $H_{XY}(Z)=H[XYZ]-H[XY]$. For (ii), $X\wedge Y$ is a1286function of $X$ and of $Y$, so with $W=X\wedge Y$ we have $H[XW]=H[X]$ and $H[WY]=H[Y]$, and (iii) for1287$X,W,Y$ reads $H[XY]+H[W]\le H[X]+H[Y]$.1288\end{proof}1289 1290The difference between the two sides of (ii) is $I(X;Y)-H[X\wedge Y]$. The meet is the part of the1291information that $X$ and $Y$ share as an observable; the mutual information can be much larger, and is1292positive for two correlated bits whose meet is trivial (\cref{exer:meet}).1293 1294\section{Feinstein's three inequalities}1295 1296The remaining lemmas of Khinchin's first chapter concern decoding. Let $r$ be a joint distribution on1297$X\times Y$ with marginals $p,q$; think of $x$ as sent and $y$ as received. The \term{maximum a posteriori}1298rule decodes $y$ as an $x$ maximizing $r(x,y)$, and its probability of error is1299\[ P_e=1-\sum_y\max_xr(x,y). \]1300 1301\begin{lemma}[Khinchin's Lemmas 2.1--2.3]\label{lem:feinstein3}1302\Scl[\cite{Fei54,Khi56}]1303\begin{enumerate}[label=(\roman*)]1304\item Let $Z\subseteq X\times Y$ with $r(Z)>1-\delta_1$ and $U_0\subseteq X$ with $p(U_0)>1-\delta_2$. For1305$\alpha>0$ let $U_1$ be the set of $x\in U_0$ with $r(\{y:(x,y)\notin Z\}\st x)\le\alpha$. Then1306$p(U_1)>1-\delta_2-\delta_1/\alpha$.1307\item If there are pairwise disjoint sets $\Delta_x\subseteq Y$ with $r(\Delta_x\st x)>1-\varepsilon$ for1308every $x$, then $P_e<\varepsilon$.1309\item (Fano's inequality.) If $|X|=n>1$, then $H(X\st Y)\le\hb(P_e)+P_e\log(n-1)$.1310\end{enumerate}1311\end{lemma}1312 1313\begin{proof}1314(i) $\sum_xp(x)\,r(\{y:(x,y)\notin Z\}\st x)=1-r(Z)<\delta_1$, so by Markov's inequality the set of $x$ where1315the conditional probability exceeds $\alpha$ has $p$-measure less than $\delta_1/\alpha$. (ii) The rule1316that decodes $y\in\Delta_x$ as $x$ is correct with probability $\sum_xp(x)\,r(\Delta_x\st x)>1-\varepsilon$, and no1317rule does better than the maximum a posteriori rule, because $\sum_yr(d(y),y)\le\sum_y\max_xr(x,y)$ for every map1318$d$. (iii) Given $y$, the posterior $r(\,\cdot\st y)$ has largest entry $1-e_y$, where $e_y$ is the conditional1319probability of error. By \cref{exer:grouping}, $H(r(\,\cdot\st y))\le\hb(e_y)+e_y\log(n-1)$. Average1320over $y$ and use the concavity of $\hb$.1321\end{proof}1322 1323Part (ii) says that a decoder is a map $d\colon Y\to X$ and that among all maps the pointwise maximizer of1324the Bayesian inverse is best. Part (iii) is the quantitative form of a triviality. If a kernel1325$f\colon X\to Y$ has a deterministic left inverse, $d\circ f=\id_X$, then $x$ is a function of $y$ and1326$H(X\st Y)=0$. Fano's inequality says that if $d\circ f$ is within $\varepsilon$ of the identity, in the1327sense that $d(y)\ne x$ with probability at most $\varepsilon$, then the equivocation is at most1328$\hb(\varepsilon)+\varepsilon\log(n-1)$. Approximate retractions lose approximately nothing.