Independent scholarship · Open accessThe monthly digest

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 781–880 of 4249. Source text is displayed literally.

781fixes the function up to a scalar. \Cref{ch:rates} returns to the R\'enyi family, which reappears when782coding is required to be exact.783 784Regularity cannot be dropped altogether. If $\ell\colon(0,1]\to\R$ satisfies $\ell(xy)=\ell(x)+\ell(y)$, then785$p\mapsto-\sum_ip_i\ell(p_i)$ satisfies the chain rule, by the same computation as for the logarithm. Using786the axiom of choice one can take $\ell=A\circ\log$ with $A$ a discontinuous additive function, and the result787is not a multiple of entropy. Measurability is enough to exclude this \cite{Lee64}.788 789\section*{Notes}790 791Shannon's axiomatic remark is in \cite[\S6]{Sha48}; Khinchin's theorem is \cite[\S2]{Khi53}. Faddeev's792theorem is \cite{Fad56}; R\'enyi \cite{Ren61} simplified the proof and introduced the entropies named793after him. The monograph of Acz\'el and Dar\'oczy \cite{AD75} surveys the functional-equation literature.794The functorial characterization is \cite{BFL11}; the operadic and categorical-algebra viewpoint is in795\cite{Lei21}, and the derivation viewpoint in \cite{Bra21}. Parzygnat \cite{Par22} gives a functorial796characterization of von Neumann entropy in the same spirit.797 798\section*{Exercises}799 800\begin{exercise}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}