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 3601–3700 of 4249. Source text is displayed literally.
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}.3621 3622\emph{Orders.} A category enriched in posets has an order on each hom-set respected by composition. The3623order on idempotents in \cref{prop:idem} is of this kind.3624 3625\section{Dagger categories and idempotents}3626 3627A \term{dagger category} is a category with an involutive identity-on-objects functor3628$\dagger\colon\CC^{\op}\to\CC$. A morphism $e\colon X\to X$ is a \term{dagger idempotent} if $e\circ e=e=e^\dagger$. It3629\term{splits} if $e=i\circ i^\dagger$ with $i^\dagger\circ i=\id$; in $\Hilb$ the dagger idempotents are the orthogonal3630projections and all of them split. Dagger idempotents on an object are partially ordered by $e\le e'$ iff3631$e\circ e'=e$. The category $\Krn$ of \cref{def:krn} is a dagger category under Bayesian inversion, and3632$L^2\colon\Krn^{\op}\to\Hilb$ is a dagger functor.3633 3634\section{Preordered semirings}3635 3636A \term{preordered semiring} is a commutative semiring with a preorder such that $a\le b$ implies3637$a+c\le b+c$ and $ac\le bc$. The conditions under which \cref{thm:strassen} holds are stated before it. The3638asymptotic preorder is $a\lesssim b$ iff $a^n\le b^{n+o(n)}$; the theorem says that it is detected by the monotone3639homomorphisms to the nonnegative reals.3640%% ---- end ch/A-toolkit.tex ----3641%% ---- begin ch/B-concordance.tex ----3642\chapter{Concordance with Khinchin}\label{app:concordance}3643 3644The table lists the sections of the two papers in \cite{Khi57} and where their subject is treated here.3645Section numbers are those of the Dover edition. The correspondence is by topic; no passage of the source is3646reproduced.3647 3648\begin{center}\small3649\renewcommand{\arraystretch}{1.22}3650\begin{longtable}{@{}p{0.47\textwidth}p{0.45\textwidth}@{}}3651\toprule3652\textbf{Khinchin} & \textbf{This book}\\\midrule3653\endhead3654\multicolumn{2}{@{}l}{\emph{The Entropy Concept in Probability Theory} (1953)}\\3655\S1 Entropy of finite schemes & \cref{ch:schemes}\\3656\S2 The uniqueness theorem & \cref{ch:uniqueness,ch:cocycle}\\3657\S3 Entropy of Markov chains & \cref{ch:sources}, \cref{prop:markov}\\3658\S4 Fundamental theorems (Theorems 2, 3) & \cref{ch:aep}, \cref{thm:mcmillan,thm:counting}\\3659\S5 Application to coding theory (Theorem 4) & \cref{ch:shannon}, \cref{thm:noiseless}\\[4pt]3660\multicolumn{2}{@{}l}{\emph{On the Fundamental Theorems of Information Theory} (1956)}\\3661Ch.~I, \S1 Two generalizations of Shannon's inequality & \cref{ch:inequalities}, \cref{lem:partial,lem:SSA}\\3662Ch.~I, \S2 Three inequalities of Feinstein & \cref{lem:feinstein3}\\3663Ch.~II, \S3 Source, stationarity, entropy & \cref{ch:sources}, \cref{prop:rate}\\3664Ch.~II, \S4 Ergodic sources & \cref{ch:ergodic}\\3665Ch.~II, \S5 The $E$ property; McMillan's theorem & \cref{ch:aep}\\3666Ch.~II, \S6 Martingales; Doob's theorem & \cref{ch:martingales}\\3667Ch.~II, \S7 Auxiliary propositions & \cref{lem:tail,lem:gk}\\3668Ch.~II, \S8 Proof of McMillan's theorem & \cref{thm:mcmillan}\\3669Ch.~III, \S9 Channel, noise, stationarity, anticipation, memory & \cref{def:channel,prop:natural}\\3670Ch.~III, \S10 Connection of the channel to the source & \cref{thm:stationary}\\3671Ch.~III, \S11 The ergodic case & \cref{ex:gap,thm:ergodicchannel}\\3672Ch.~IV, \S\S12--13 Feinstein's fundamental lemma & \cref{ch:feinstein}, \cref{thm:feinstein,thm:feinsteinmem}\\3673Ch.~V, \S14 Coding & \cref{ch:shannon}\\3674Ch.~V, \S15 The first Shannon theorem & \cref{thm:shannon1}\\3675Ch.~V, \S16 The second Shannon theorem & \cref{thm:shannon2}\\3676Conclusion & \cref{thm:capacities}, \cref{ch:coda}\\3677\bottomrule3678\end{longtable}3679\end{center}3680 3681\noindent Topics treated here that have no counterpart in the source: the functorial and operadic3682characterizations of entropy (\cref{ch:uniqueness}); information cohomology and entropy modulo a prime3683(\cref{ch:cocycle}); relative entropy and the enriched structure (\cref{ch:inequalities}); coalgebraic sources3684(\cref{ch:sources}); the categorical ergodic decomposition (\cref{ch:ergodic}); the converse coding theorem and3685polar codes (\cref{ch:shannon}); zero-error capacity, asymptotic spectra and the isomorphism theory of3686Bernoulli shifts (\cref{ch:rates}).3687%% ---- end ch/B-concordance.tex ----3688%% ---- begin ch/C-computations.tex ----3689\chapter{Computational Checks}\label{app:computations}3690 3691The script \texttt{verify.py} that accompanies this book recomputes every numerical example in the text3692and in the solutions, and tests a number of structural claims on explicit or randomly generated finite3693instances. It uses only the Python standard library, fixes its random seed, and runs in about a second;3694\texttt{python3 verify.py} prints one line per check and exits with status zero if and only if all pass.3695Version~1.0 performs 91 checks, all of which pass under Python~3.8 or later.3696 3697A check of this kind is evidence about the examples and about the absence of slips in the finite3698statements. It is not a proof of any theorem, and the theorems tagged \textsf{classical} or3699\textsf{literature} rest on the references cited for them. What the script does establish is the3700following.