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 801–900 of 4249. Source text is displayed literally.
801Carry out the second step of Khinchin's proof for $p=(\tfrac12,\tfrac13,\tfrac16)$: describe the joint802distribution $r$, and verify numerically that $\log g-\sum_ip_i\log g_i=H(p)$.803\end{exercise}804 805\begin{exercise}\label{exer:recursive}806Show that symmetry and Faddeev's recursivity imply $H(p\circ_iq)=H(p)+p_iH(q)$ for all $q\in\Delta_k$, by807induction on $k$, and deduce the full chain rule.808\end{exercise}809 810\begin{exercise}811Show that $H_\alpha$ is additive on products and satisfies \textup{(K1)} and \textup{(K3)}. Compute812$\lim_{\alpha\to1}H_\alpha(p)$.813\end{exercise}814 815\begin{exercise}\label{exer:renyifunctor}816Any function $I$ on objects of $\FinProb$ that is invariant under isomorphism defines a functor to $(\R,+)$817by $F(f)=I(p)-I(q)$. Show that for $I=H_2$ this functor is continuous and takes values in $[0,\infty)$, and818exhibit a failure of convex-linearity. Which step of the proof of \cref{thm:BFL} breaks?819\end{exercise}820 821\begin{exercise}822Let $I$ satisfy \eqref{eq:leibniz} for all $p$, $q$ and $i$. Show that $I(u_1)=0$, that $I(1,0)=0$, and that823$I$ satisfies the full chain rule.824\end{exercise}825%% ---- end ch/02-uniqueness.tex ----826%% ---- begin ch/03-cocycle.tex ----827\chapter{Entropy as a Cocycle}\label{ch:cocycle}828 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*}