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 1281–1380 of 4249. Source text is displayed literally.
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.1329\Cref{ch:feinstein} is built on this notion.1330 1331\section{Relative entropy as a functor}1332 1333Entropy is a functor on $\FinProb$ (\cref{thm:functor}) and is characterized by that1334(\cref{thm:BFL}). Relative entropy has the same status on a slightly larger category. Let $\FinStat$ have1335finite probability spaces as objects; a morphism $(X,p)\to(Y,q)$ is a pair $(f,s)$ of a1336measure-preserving map $f\colon X\to Y$ and a kernel $s\colon Y\to X$ with $f\circ s=\id_Y$, thought of as a1337hypothesis about how $x$ is distributed given $f(x)$. Composition is $(g,t)\circ(f,s)=(g\circ f,s\circ t)$.1338 1339\begin{theorem}[Baez--Fritz]\label{thm:BF}1340\Sli[\cite{BF14}] The assignment $(f,s)\mapsto\KL p{s\circ q}$ is a functor $\FinStat\to[0,\infty]$. It is lower1341semicontinuous and convex-linear, and it vanishes when $s$ is the Bayesian inverse of $f$. Every functor1342with these properties is a constant multiple of it.1343\end{theorem}1344 1345Functoriality here is \cref{prop:chainD}. The quantity $\KL p{s\circ q}$ is the information gained on learning1346that the true distribution is $p$, when one's prior was built from the correct marginal $q$ and the1347hypothesis $s$.1348 1349\section{Beyond the elementary inequalities}1350 1351Every inequality proved so far is a consequence of \cref{prop:submodular}, that is, of monotonicity and1352submodularity. Such consequences are called Shannon-type. They are all there is for up to three variables.1353 1354\begin{theorem}\label{thm:nonshannon}1355\Scl[\cite{ZY98,Mat07}] For four or more random variables there are linear inequalities among their joint1356entropies that hold for all distributions and are not consequences of monotonicity and submodularity;1357there are infinitely many independent ones, and the closure of the set of entropy vectors is a convex1358cone that is not polyhedral.1359\end{theorem}1360 1361Khinchin's elementary inequalities are thus the first layer of a structure that is not finitely describable.1362Neither the cohomological account of \cref{ch:cocycle} nor the enriched one of this chapter explains the1363further layers. We record this as a limit of what is understood, not of what was needed: the coding1364theorems use only the first layer.1365 1366\section*{Notes}1367 1368Relative entropy is due to Kullback and Leibler; for the classical theory see \cite{CT06,CK11}. The1369enriched-category view of data processing and \cref{prop:copy} are due to Perrone \cite{Per24}. The1370generalized Shannon inequalities and Feinstein's lemmas are \cite[Ch.~I]{Khi56}, after \cite{Fei54}; Fano's1371inequality is in \cite{Fan61}. Submodularity of entropy and the polymatroid point of view go back to1372Fujishige \cite{Fuj78}; non-Shannon inequalities were discovered by Zhang and Yeung \cite{ZY98}, and the1373non-polyhedrality is due to Mat\'u\v{s} \cite{Mat07}. See \cite{Yeu08} for the whole subject. The category1374$\FinStat$ and \cref{thm:BF} are from \cite{BF14}.1375 1376\section*{Exercises}1377 1378\begin{exercise}1379For $p=(\tfrac12,\tfrac12)$ and $q=(\tfrac14,\tfrac34)$ compute $\KL pq$ and $\KL qp$. Let $f$ be the binary1380symmetric channel that flips its input with probability $0.1$. Compute $\KL{f\circ p}{f\circ q}$ and compare.