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 829–928 of 4249. Source text is displayed literally.
829The chain rule $H(AB)=H(A)+H_A(B)$ has the shape of a cocycle condition: the value on a product is the value830on the first factor plus the value on the second, transported by the first. Baudot and Bennequin made this831precise. Observables form a monoid, the monoid acts on functions of probability laws by conditioning, and832entropy is a 1-cocycle for this action. The uniqueness theorem becomes the computation of a cohomology833group. This chapter develops the theory in the simplest setting in which it is nontrivial, a finite sample834space with all its partitions, where everything can be done by hand.835 836\section{Observables}837 838Let $\Omega$ be a finite set. An \term{observable} is a partition $X$ of $\Omega$; one thinks of the quotient839map $\Omega\to\Omega/X$ as a random variable, and of two random variables as the same observable when each is840a function of the other. Say that $X$ \term{refines} $Y$ if every block of $X$ lies in a block of $Y$, so that841$Y$ is a function of $X$. The \term{product} $XY$ is the coarsest common refinement, whose blocks are the842nonempty intersections $B\cap C$ of a block of $X$ with a block of $Y$; it is the observable ``$X$ and $Y$843jointly''. The trivial partition $1$ is a unit. Under this product the set $\Pi(\Omega)$ of observables is a844commutative monoid in which every element is idempotent:845\[ XY=YX,\qquad XX=X,\qquad 1X=X. \]846$X$ refines $Y$ iff $XY=X$.847 848\begin{figure}[ht]\centering849\begin{tikzpicture}[x=1cm,y=1cm]850 \node (top) at (0,2.4) {$a\,|\,b\,|\,c$};851 \node (ya) at (-2.6,1.2) {$a\,|\,bc$};852 \node (yb) at (0,1.2) {$b\,|\,ac$};853 \node (yc) at (2.6,1.2) {$c\,|\,ab$};854 \node (one) at (0,0) {$abc$};855 \draw[thick] (top) -- (ya) -- (one) -- (yc) -- (top);856 \draw[thick] (top) -- (yb) -- (one);857 \node[lab,ink2] at (-3.6,1.2) {$Y_a$};858 \node[lab,ink2] at (0.9,1.2) {$Y_b$};859 \node[lab,ink2] at (3.6,1.2) {$Y_c$};860 \node[lab,ink2] at (0.7,0) {$1$};861\end{tikzpicture}862\caption{The five observables on a three-point set, ordered by refinement. The product of any two of the863binary observables $Y_a,Y_b,Y_c$ is the atomic observable at the top. This is the smallest structure on864which the chain rule has content, and \cref{thm:H1} is proved by reduction to it.}\label{fig:three}865\end{figure}866 867A \term{law} is a probability measure $P$ on $\Omega$. The law of an observable $X$ under $P$ is the868distribution $X_*P$ on the set of blocks of $X$. For a block $B$ with $P(B)>0$ we write $P|_B$ for the869conditional law.870 871\section{The conditioning action}872 873Let $\Fun$ be the vector space of measurable real functions on the simplex $\Delta(\Omega)$ of laws. For an874observable $Y$ and $f\in\Fun$ define875\begin{equation}\label{eq:action}876 (Y.f)(P)=\sum_{B\in Y,\ P(B)>0}P(B)\,f\bigl(P|_B\bigr).877\end{equation}878This is the average of $f$ after $Y$ has been observed.879 880\begin{lemma}\label{lem:action}881\Sli[\cite{BB15}] Formula \eqref{eq:action} is an action of the monoid $\Pi(\Omega)$ on $\Fun$: $1.f=f$ and882$Y.(Z.f)=(YZ).f$.883\end{lemma}884 885\begin{proof}886$(Y.(Z.f))(P)=\sum_BP(B)\sum_CP|_B(C)\,f\bigl((P|_B)|_C\bigr)=\sum_{B,C}P(B\cap C)\,f\bigl(P|_{B\cap C}\bigr)$, the sums being over887blocks with positive probability.888\end{proof}889 890Call $f\in\Fun$ \term{$X$-local} if $f(P)$ depends only on the law $X_*P$ of $X$, and write $\Fun_X$ for the891space of such functions. A function that is local for an observable is local for every refinement of it.892If $f$ is $Z$-local then $Y.f$ is $YZ$-local, because the law of $YZ$ determines the probabilities of the893blocks of $Y$ and the law of $Z$ under each conditional law.894 895\section{The complex}896 897\begin{definition}\label{def:complex}898An \term{$n$-cochain} is a family $f=\bigl(f[Y_1|\cdots|Y_n]\bigr)$, indexed by $n$-tuples of observables, with899$f[Y_1|\cdots|Y_n]\in\Fun_{Y_1\cdots Y_n}$. The coboundary of $f$ is the $(n+1)$-cochain900\begin{align*}901(\delta f)[Y_1|\cdots|Y_{n+1}]={}&Y_1.f[Y_2|\cdots|Y_{n+1}]902 +\sum_{k=1}^n(-1)^kf[Y_1|\cdots|Y_kY_{k+1}|\cdots|Y_{n+1}]\\903 &+(-1)^{n+1}f[Y_1|\cdots|Y_n].904\end{align*}905The cohomology of the complex $(C^\bullet,\delta)$ is the \term{information cohomology} $H^\bullet(\Omega)$ of906the full structure on $\Omega$.907\end{definition}908 909This is the standard complex computing the cohomology of a monoid with coefficients in a module, cut down910by the locality condition. That $\delta\delta=0$ is the usual computation, using \cref{lem:action}, and the911remark on locality shows that $\delta$ preserves the condition. A $0$-cochain is a function local for the912trivial observable, that is, a constant, so $C^0=\R$.913 914In low degrees, for a constant $c$ and a 1-cochain $f$,915\[ (\delta c)[Y]=Y.c-c=0,\qquad (\delta f)[Y|Z]=Y.f[Z]-f[YZ]+f[Y]. \]916The first vanishes because $\sum_BP(B)=1$. Thus $H^0(\Omega)=\R$, there are no nonzero 1-coboundaries, and a9171-cochain is a cocycle exactly when918\begin{equation}\label{eq:cocycle}919 f[YZ]=f[Y]+Y.f[Z]\qquad\text{for all observables $Y,Z$.}920\end{equation}921 922\begin{proposition}\label{prop:Hcocycle}923\Sli[\cite{BB15}] The family $H[Y](P)=H(Y_*P)$ is a 1-cocycle.924\end{proposition}925 926\begin{proof}927It is local by definition, and \eqref{eq:cocycle} for it is \cref{prop:properties}(iii) applied to the joint law928of $Y$ and $Z$: the term $(Y.H[Z])(P)=\sum_BP(B)\,H\bigl(Z_*(P|_B)\bigr)$ is Khinchin's $H_Y(Z)$.