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

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$.3561 3562$\CC$ \term{has conditionals} if every morphism into a tensor product $X\otimes Y$ factors as its marginal on3563$X$ followed by a morphism that produces $Y$ from $X$ and the input. In $\BorelStoch$ conditionals exist; this3564is the existence of regular conditional probabilities. A \term{Bayesian inverse} of $f\colon X\to Y$ with3565respect to a state $p$ is a morphism $f^\dagger\colon Y\to X$ with $(f\circ p)\rtimes f^\dagger$ equal to $p\rtimes f$ after3566exchanging the factors. Two morphisms $f,g\colon X\to Y$ are equal \term{$p$-almost surely} if3567$p\rtimes f=p\rtimes g$.3568 3569An infinite tensor product $\bigotimes_{i\in I}X_i$ is a \term{Kolmogorov product} if it is the limit of the finite3570tensor products with their marginalization maps, the limit is preserved by tensoring with any object, and3571the projections to finite subproducts are deterministic \cite{FR20}. In $\BorelStoch$ countable Kolmogorov3572products exist and are the usual product spaces.3573 3574For a category $D$ and a Markov category $\CC$, the functors $D\to\CC_{\det}$, with natural transformations whose3575components are arbitrary morphisms of $\CC$, form a Markov category \cite[\S7]{Fri20}. $\Dyn$ is the case in3576which $D$ is the group $\Z$ regarded as a category with one object.3577 3578\section{Operads}3579 3580A \term{symmetric operad} $P$ in a symmetric monoidal category consists of objects $P(n)$, $n\ge0$, of3581$n$-ary operations with actions of the symmetric groups, a unit in $P(1)$, and composition maps3582\[ P(m)\otimes P(k_1)\otimes\dots\otimes P(k_m)\longrightarrow P(k_1+\dots+k_m) \]3583that are associative, unital and equivariant. The \term{partial composite} $p\circ_iq$ inserts $q$ into the3584$i$-th input of $p$ and units into the others. The operad $\Delta$ of simplices has $\Delta(n)=\Delta_n$, the3585simplex of distributions on $n$ points, with the composition of \cref{ch:schemes}; it is an operad in3586topological spaces. Its algebras in sets or spaces are the convex spaces.3587 3588Given an operad $P$ in an additive setting and a bimodule $M$ over it, a \term{derivation} is a family of3589maps $d\colon P(n)\to M(n)$ with $d(p\circ_iq)=dp\circ_iq+p\circ_idq$. In \cref{thm:derivation} the bimodule is3590$\R$ in every arity, with $p\circ_ir=p_ir$ and $r\circ_iq=r$.3591 3592\section{Cohomology of a monoid}3593 3594Let $S$ be a monoid acting on an abelian group $F$. The complex of inhomogeneous cochains has3595$C^n=\{f\colon S^n\to F\}$ and coboundary3596\begin{align*}3597 (\delta f)(s_1,\dots,s_{n+1})={}&s_1.f(s_2,\dots,s_{n+1})+\sum_{k=1}^n(-1)^kf(\dots,s_ks_{k+1},\dots)\\3598 &+(-1)^{n+1}f(s_1,\dots,s_n).3599\end{align*}3600Its cohomology is $\Ext^\bullet_{\Z[S]}(\Z,F)$. A 1-cocycle is a \term{crossed homomorphism},