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

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.3701 3702\begin{center}\small3703\renewcommand{\arraystretch}{1.25}3704\begin{longtable}{@{}p{0.09\textwidth}p{0.83\textwidth}@{}}3705\toprule3706\textbf{Ch.} & \textbf{What is checked}\\\midrule3707\endhead3708\ref{ch:schemes} & \Cref{ex:first,ex:coarse}. On random instances: $H(f)=H(p)-H(q)$ and functoriality3709 (\cref{thm:functor}); the operadic chain rule; convex-linearity (\cref{prop:convexlinear}); Khinchin's3710 properties; \cref{prop:lossnoise}.\\3711\ref{ch:uniqueness} & The second step of Khinchin's proof on random rational distributions. Additivity,3712 maximality and expansibility of the R\'enyi entropies, their limit at $\alpha=1$, and \cref{ex:renyi}. The3713 Leibniz rule \eqref{eq:leibniz} for $H$ and its failure for $H_2$.\\3714\ref{ch:cocycle} & On random observables and laws on a five-point space: the action axiom for3715 $\alpha=1,\tfrac12,2$ (\cref{lem:action}); the cocycle condition for entropy (\cref{prop:Hcocycle});3716 $\delta\delta=0$ on a generic local cochain; the Tsallis coboundary and cocycle identities and the limit3717 $\alpha\to1$ (\cref{thm:tsallis,prop:obstruction}). The fundamental equation for $\hb$ and for $h(x)=x$, and,3718 in a four-dimensional test space, that its solutions are spanned by $\hb$. The Leibniz rule for the Fermat3719 quotient; that entropy modulo $p$ is well defined, satisfies the chain rule, equals the truncated3720 logarithm and satisfies the fundamental equation, for $p=3,5,7,11,13$ (\cref{thm:modp}).\\