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

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},3601$f(st)=f(s)+s.f(t)$, and a 1-coboundary has the form $f(s)=s.c-c$. The complex of \cref{def:complex} is the3602subcomplex of local cochains for the monoid of observables acting on functions of laws by conditioning. In3603the general setting of \cite{Vig20} the monoid varies over a poset and the computation is carried out for3604modules over a presheaf of algebras, in the topos of presheaves on that poset.3605 3606\section{Enrichment}3607 3608A category is \term{enriched} in a monoidal category $\mathcal{V}$ when its hom-sets are objects of3609$\mathcal{V}$ and composition is a morphism of $\mathcal{V}$. Three cases occur in the text.3610 3611\emph{Divergences.} A \term{divergence space} is a set $X$ with a function $D\colon X\times X\to[0,\infty]$ vanishing3612on the diagonal; a morphism is a map that does not increase $D$; the tensor product is the product of sets3613with the sum of the divergences. A category enriched in divergence spaces is one in which3614$D(g\circ f\,\|\,g'\circ f')\le D(f\,\|\,f')+D(g\,\|\,g')$. For a Markov category one asks in addition that the tensor3615product of morphisms be short \cite{Per24}. When $D$ is symmetric and satisfies the triangle inequality this3616is enrichment in metric spaces in the sense of Lawvere \cite{Law73}.3617 3618\emph{Topologies.} A category is enriched in topological spaces, with the canonical closed structure, when3619its hom-sets are spaces and composition is separately continuous. This is the enrichment used in3620\cite{PVB24}.