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

3461ergodic 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]3489\Spg Entropy over $\R$ and over $\Fp$ are both the defect of additivity of a derivation3490(\cref{ch:cocycle}), and both are unique solutions of the chain rule. Give a single construction, for a3491suitable class of rings with a derivation-like operator, of which both are instances, and identify the3492cohomology theory in which the resulting class lives. The appearance of the same functional equation in3493the theory of polylogarithms \cite{Cat88,Kon95,EVG02} suggests where to look.3494\end{problem}3495 3496\begin{problem}[Cohomology of processes]3497\Spg Extend information cohomology to the observables of a stationary source, with the shift acting. Is the3498entropy rate a class in an equivariant theory, and is its affinity (\cref{thm:affine}) a vanishing statement?3499\end{problem}3500 3501\begin{problem}[The collapse of the spectrum]3502\Spg Define a preordered semiring of channels in which the preorder is simulation up to a tolerance, and3503prove that its asymptotic spectrum, in the sense of \cref{thm:strassen} or of a suitable extension, is the3504single point $W\mapsto2^{C(W)}$. \Cref{thm:universal,prop:collapse} are evidence that such a statement holds. The3505difficulty is that a preorder defined with a tolerance is not transitive without loss.3506\end{problem}3507 3508\begin{problem}[Existence]3509\Spg Find a structural proof of Feinstein's lemma: a general principle, valid in a class of enriched Markov3510categories, that produces approximate retractions from the concentration of an information density. The3511polar construction of \cref{ch:shannon} is structural but special. Is there a version of it for channels3512with memory in which the martingale is indexed by the tower of \cref{prop:natural}?3513\end{problem}3514 3515\begin{problem}[Ergodic morphisms]3516\Spg Characterize, in terms of the invariant quotients of \cref{thm:MP}, the morphisms $\nu$ of $\Dyn$ for3517which the compound source with every ergodic source is ergodic. The natural conjecture is that this holds3518iff the invariant quotient of the compound system is, almost surely, that of its input; \cref{ex:gap} is a3519channel for which it is strictly larger.3520\end{problem}3521 3522\section*{Notes}3523 3524Khinchin's own summary is the Conclusion of \cite{Khi56}. For the programme of synthetic probability3525theory in Markov categories, of which several of the problems above would be instances, see \cite{Fri20} and3526the works cited in \cref{ch:ergodic,ch:martingales}, in particular the synthetic laws of large numbers of3527\cite{FGLPS26}, which are the nearest existing results to the first problem.3528%% ---- end ch/13-coda.tex ----3529\appendix3530%% ---- begin ch/A-toolkit.tex ----3531\chapter{Categorical Toolkit}\label{app:toolkit}3532 3533This appendix collects the definitions used in the text. It is a reminder, not an introduction.3534 3535\section{Markov categories}3536 3537A \term{Markov category} is a symmetric monoidal category $(\CC,\otimes,1)$ in which every object $X$ carries3538a commutative comonoid structure3539\[ \cpy_X\colon X\to X\otimes X,\qquad\del_X\colon X\to1, \]3540compatible with the tensor product, and in which $\del$ is natural: $\del_Y\circ f=\del_X$ for every $f\colon X\to Y$.3541Equivalently the unit object is terminal. Morphisms $1\to X$ are called \term{states}. A morphism $f$ is3542\term{deterministic} if it also commutes with copying, $\cpy_Y\circ f=(f\otimes f)\circ\cpy_X$. The deterministic3543morphisms form a cartesian monoidal subcategory $\CC_{\det}$.3544 3545\begin{center}\small3546\renewcommand{\arraystretch}{1.2}3547\begin{tabular}{@{}lll@{}}3548\toprule3549\textbf{Category} & \textbf{Objects} & \textbf{Morphisms}\\\midrule3550$\FinStoch$ & finite sets & stochastic matrices\\3551$\BorelStoch$ & standard Borel spaces & Markov kernels\\3552$\Stoch$ & measurable spaces & Markov kernels\\3553$\Dyn$ & the same, with an automorphism & equivariant Markov kernels\\3554\bottomrule3555\end{tabular}3556\end{center}3557 3558In $\FinStoch$ and $\BorelStoch$ the deterministic morphisms are the (measurable) maps; in $\Stoch$ they are the3559kernels taking only the values $0$ and $1$. For a state $p$ on $X$ and a morphism $f\colon X\to Y$ the joint3560state $p\rtimes f=(\id\otimes f)\circ\cpy\circ p$ on $X\otimes Y$ has marginals $p$ and $f\circ p$.