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 889–988 of 4249. Source text is displayed literally.
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)$.929\end{proof}930 931So Khinchin's property~2 is literally the cocycle condition. Two features of the formalism deserve notice932before we compute. The cocycle condition is imposed for a fixed sample space and all pairs of observables933on it, whereas Khinchin's theorem quantifies over all finite schemes; we shall see that three points934suffice. And since $YZ=ZY$, a cocycle satisfies935\begin{equation}\label{eq:symm}936 f[Y]+Y.f[Z]=f[Z]+Z.f[Y],937\end{equation}938which is a nontrivial constraint relating the values on $Y$ and on $Z$. Symmetry of entropy in its939arguments, an axiom in \cref{ch:uniqueness}, will come out of the commutativity of the monoid.940 941\section{The fundamental equation}942 943\begin{theorem}[Tverberg, Kendall, Lee]\label{thm:FEITH}944\Scl[\cite{Tve58,Ken64,Lee64}; see \cite{AD75}] Let $h\colon[0,1]\to\R$ be measurable with $h(1)=0$, and945suppose that946\begin{equation}\label{eq:FEITH}947 h(x)+(1-x)\,h\Bigl(\frac{y}{1-x}\Bigr)=h(y)+(1-y)\,h\Bigl(\frac{x}{1-y}\Bigr)948\end{equation}949for all $x,y\in[0,1)$ with $x+y\le1$. Then $h=c\,\hb$ for a constant $c$, where950$\hb(x)=-x\log x-(1-x)\log(1-x)$.951\end{theorem}952 953Equation \eqref{eq:FEITH} is called the fundamental equation of information theory. The condition954$h(1)=0$ cannot be omitted, since $h(x)=x$ is a solution. The binary entropy satisfies the equation because955both sides compute $H(x,y,1-x-y)$, by splitting off first one outcome and then the other.956 957\begin{theorem}\label{thm:H1}958\Sli[\cite{BB15,Vig20}; in this form proved here] Let $|\Omega|\ge3$. Every 1-cocycle is a constant multiple of959entropy. Hence960\[ H^0(\Omega)\iso\R,\qquad H^1(\Omega)\iso\R\cdot[H]. \]961\end{theorem}962 963\begin{proof}964Let $f$ be a 1-cocycle.965 966\emph{Step 0: normalization.} Taking $Y=Z$ in \eqref{eq:cocycle} and using $YY=Y$ gives $Y.f[Y]=0$, that is,967$\sum_BP(B)\,f[Y](P|_B)=0$ for all $P$. Under $P|_B$ the observable $Y$ is constant, so by locality968$f[Y](P|_B)$ is a number $c_B$ depending only on $B$. Then $\sum_BP(B)c_B=0$ for all $P$ forces $c_B=0$: a969cocycle vanishes at laws under which its argument is deterministic. In particular $f[1]=0$.970 971\emph{Step 1: three points.} Let $\Omega=\{a,b,c\}$ and let $Y_a$ be the partition $\{a\}\,|\,\{b,c\}$, and972similarly $Y_b,Y_c$. By locality $f[Y_a](P)=h_a(P(a))$ for a measurable function $h_a$ on $[0,1]$, and by973Step~0, $h_a(0)=h_a(1)=0$. Evaluate \eqref{eq:symm} for $Y_a,Y_c$ at the law $P=(x,1-x-y,y)$. Conditioning on974$\{a\}$ makes $Y_c$ deterministic; conditioning on $\{b,c\}$ gives $c$ the probability $y/(1-x)$. So975\[ h_a(x)+(1-x)\,h_c\Bigl(\frac{y}{1-x}\Bigr)=h_c(y)+(1-y)\,h_a\Bigl(\frac{x}{1-y}\Bigr). \]976Putting $y=1-x$ gives $h_a(x)=h_c(1-x)$. The same argument for the other two pairs gives977$h_a(x)=h_b(1-x)$ and $h_b(x)=h_c(1-x)$. Hence $h_a=h_b=h_c=h$ with $h(x)=h(1-x)$, and $h$ satisfies978\eqref{eq:FEITH}. By \cref{thm:FEITH}, $h=c\,\hb$, so $f[Y]=cH[Y]$ for the three binary observables. The979atomic observable is $Y_aY_c$, and \eqref{eq:cocycle} gives $f[Y_aY_c]=c\,(H[Y_a]+Y_a.H[Y_c])=cH[Y_aY_c]$.980 981\emph{Step 2: the general case.} Let $W$ be a partition of $\Omega$ into three blocks. The observables982refined by $W$, with the laws of $W$, form a copy of the three-point structure, because all the functions983involved are $W$-local and every distribution on three points is the law of $W$ under some $P$. So there is984a constant $c_W$ with $f[Y]=c_WH[Y]$ for every $Y$ refined by $W$. If two such partitions $W,W'$ both refine985a binary observable $Y$, then $c_W=c_{W'}$, since $H[Y]\ne0$. Any two binary observables $\{A,A^c\}$ and986$\{B,B^c\}$ are connected in this way: if the two are nested, say $A\subsetneq B$, both are refined by987$\{A,B\setminus A,B^c\}$; otherwise $A\cap B$ is a proper nonempty subset of both $A$ and $B$ and988$\{A\cap B,(A\cap B)^c\}$ is nested with each. Since $|\Omega|\ge3$, every binary observable is refined by