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

3389 3390That such invariants exist, are finite, and are given by the formulas $-\sum p\log p$ and $\max I$ is the3391content of the theory. The formula for entropy is forced by the chain rule, which is a cocycle condition.3392The existence of the limits is McMillan's theorem and Feinstein's lemma.3393 3394\section{What became formal}3395 3396The following statements, each of which costs Khinchin a computation, came out of general principles.3397 3398\begin{center}\small3399\renewcommand{\arraystretch}{1.25}3400\begin{tabular}{@{}p{0.43\textwidth}p{0.49\textwidth}@{}}3401\toprule3402\textbf{Statement} & \textbf{Mechanism}\\\midrule3403$H(AB)=H(A)+H_A(B)$ & functoriality of $H$ on $\FinProb$; the cocycle condition\\3404symmetry of entropy & commutativity of the monoid of observables\\3405uniqueness of entropy & $H^1(\Omega)\iso\R$, given the regularity theorem for the fundamental equation\\3406Shannon's inequality and its generalizations & positivity of relative entropy and the chain rule\\3407data processing & composition is short: the enrichment\\3408the compound source is stationary & morphisms of $\Dyn$ compose\\3409absence of anticipation & naturality between towers\\3410ergodic decomposition & disintegration over the invariant quotient\\3411convergence of conditional probabilities, in mean & monotone sequences of idempotents converge\\3412McMillan's theorem, in mean & chain rule, two idempotent limits, one tail estimate\\3413the second Shannon theorem & Fano's inequality: near-retractions lose little\\3414the converse & any monotone subadditive normalized function bounds the rate\\3415\bottomrule3416\end{tabular}3417\end{center}3418 3419\section{What did not}3420 3421Five things resisted, and they are the mathematical substance of the subject.3422 3423\emph{The regularity theorem.} \Cref{thm:H1} reduces uniqueness to the statement that measurable solutions of3424the fundamental equation are multiples of the binary entropy. That statement is analysis, and without a3425regularity hypothesis it is false. Cohomology organizes the theorem; it does not prove it.3426 3427\emph{Almost sure convergence.} The theorems of Doob, Birkhoff and Breiman need maximal inequalities. The3428categorical convergence results currently available are in norm. For the coding theorems this is enough,3429which is itself worth knowing, but the gap is real.3430 3431\emph{The tail estimate.} \Cref{lem:tail} is three lines and elementary, and the proof of McMillan's theorem3432cannot do without it or something like it. It is the point at which the logarithm, which is unbounded,3433meets a convergence theory built for bounded functions.3434 3435\emph{Feinstein's lemma.} The one-shot lemma is a greedy construction and a counting bound. We gave its3436statement a categorical form and proved nothing about it by categorical means. The same is true of the3437strong converse.3438 3439\emph{Ergodicity of the compound source.} Here the categorical formulation did something useful, in that3440it made visible the difference between an equivariant map into a sequence space and an equivariant kernel,3441and so located the hypothesis missing from Khinchin's theorem. But the theorem with the hypothesis restored3442is proved by a mixing computation.3443 3444\section{How much of it is higher}3445 3446The title of this series promises higher categories, and the reader is owed an account. \Cref{ch:uniqueness,ch:cocycle}3447use operads and the cohomology of a monoid with coefficients in a module over a presheaf of algebras; that3448is homological algebra in a topos, and the deformation argument of \cref{prop:obstruction} is of the kind for3449which derived language exists. Everything from \cref{ch:inequalities} on uses monoidal categories with one3450layer of extra structure on the hom-sets: a divergence, a topology, or an order. These are enriched3451categories and so are two-dimensional in a weak sense, but no coherence beyond dimension one was used, and3452no homotopy type appeared that was not a set. The approximate retractions of \cref{ch:feinstein} suggest a3453setting in which morphisms are considered up to a controlled error and composition holds up to a larger3454one; we did not build it.3455 3456\section{Khinchin, seventy years on}3457 3458His definitions stand. A source is a stationary measure on a sequence space, a channel is a stationary3459kernel, and the theorems are about these. Three points have changed. His finite-memory condition does not3460imply what he uses it for; an independence condition on the noise must be added (\cref{ch:channels}). His3461ergodic capacity is the same as the capacity defined with all stationary sources, which he left open3462(\cref{thm:capacities}). And he proves no converse, so that his capacity is shown to be achievable and not3463shown to be a limit; the converse is easier than anything he does prove (\cref{thm:converse}). His use of3464almost sure theorems where convergence in mean suffices is a matter of economy, not of correctness.3465 3466\section{Open problems}3467 3468\begin{problem}[A synthetic McMillan theorem]3469\Spg Formulate and prove the asymptotic equipartition property inside a Markov category with Kolmogorov3470products, a dagger on its category of probability spaces, and enrichments in topological spaces and in3471divergence spaces, from axioms satisfied by measure-theoretic probability. The proof in \cref{ch:aep}3472indicates the ingredients. What is missing is a derivation of the mean ergodic theorem in the framework of3473\cite{PVB24}, where the Ces\`aro averages are not a monotone net, and an account of how the two3474enrichments interact, which is where \cref{lem:tail} would have to live.3475\end{problem}3476 3477\begin{problem}[Maximal inequalities]3478\Spg Find a categorical formulation of almost sure convergence in which the theorems of Doob and Birkhoff,3479and with them the Shannon--McMillan--Breiman theorem, have proofs comparable in length to their3480counterparts in mean.3481\end{problem}3482 3483\begin{problem}[Higher information cohomology]3484\Spg Compute $H^n(\Omega)$ for $n\ge2$ for the full structure on a finite set. Decide whether the non-Shannon3485inequalities of \cref{thm:nonshannon}, which no first-order structure explains, are reflected in it.3486\end{problem}3487 3488\begin{problem}[Entropy over other bases]