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

3321\end{example}3322 3323\section{Other entropies}3324 3325Several notions that carry the name entropy arise from categorical constructions of the same general3326shape, a growth rate attached to an endomorphism. Dimitrov, Haiden, Katzarkov and Kontsevich define the3327entropy of an exact endofunctor of a triangulated category as the growth rate of the complexity of the3328images of a generator under its powers \cite{DHKK14}. Dikranjan and Giordano Bruno derive the topological,3329measure-theoretic and algebraic entropies from a single functorial scheme \cite{DGB13}. We mention them to3330mark the boundary of this book: they generalize the entropy of \cref{thm:KS}, an invariant of a3331dynamical system, and not the coding theorems.3332 3333\section*{Notes}3334 3335Zero-error capacity was introduced by Shannon \cite{Sha56}; the pentagon was settled by Lov\'asz3336\cite{Lov79}. Asymptotic spectra are due to Strassen \cite{Str88}, and their application to graphs to3337Zuiddam \cite{Zui19}. The resource-theoretic point of view on rates is developed in \cite{CFS16,Fri17}. Error3338exponents and their expression through R\'enyi entropies are treated in \cite{CK11}. For the isomorphism3339theory of Bernoulli shifts see \cite{Orn70,Gla03}; for symbolic dynamics and constrained channels,3340\cite{LM95}.3341 3342\section*{Exercises}3343 3344\begin{exercise}3345Verify that $\alpha(C_5)=2$ and that the words $(i,2i)$, $i\in\Z/5$, are pairwise non-confusable for two uses of3346the channel of \cref{ex:pentagon}. Find the capacity-achieving input and confirm $C=\log5-1$.3347\end{exercise}3348 3349\begin{exercise}\label{exer:schur}3350Show that if $q=Dp$ for a doubly stochastic matrix $D$ then $H_\alpha(q)\ge H_\alpha(p)$ for every $\alpha\ge0$.3351Deduce that if $q^{\otimes m}=Dp^{\otimes n}$ for a doubly stochastic $D$ then $nH_\alpha(p)\le mH_\alpha(q)$ for all3352$\alpha$.3353\end{exercise}3354 3355\begin{exercise}3356Prove \cref{thm:exponent}(i). For $p=(0.9,0.1)$ and $R=0.7$, compute the exponent in \cref{thm:exponent}(iii) and3357compare it with $\KL{(1-\tau,\tau)}{p}$, where $\hb(\tau)=R$ and $0.1<\tau<\tfrac12$.3358\end{exercise}3359 3360\begin{exercise}3361Prove the claims of \cref{ex:golden}: count the allowed blocks, and maximize the entropy of a Markov chain on3362$\{0,1\}$ with $q_{11}=0$.3363\end{exercise}3364 3365\begin{exercise}3366Compute the entropies of $B(\tfrac12,\tfrac12)$, $B(\tfrac13,\tfrac13,\tfrac13)$ and Meshalkin's two shifts. Which3367of the four is a factor of which?3368\end{exercise}3369%% ---- end ch/12-rates.tex ----3370\part{Assessment}3371%% ---- begin ch/13-coda.tex ----3372\chapter{What the Language Buys}\label{ch:coda}3373 3374Khinchin's conclusion to his second paper says that the proof he has given is long and complicated but3375rests on a single idea, and he restates the idea in two pages. This chapter attempts the same for the3376present book, and then says where its method stopped working.3377 3378\section{The idea}3379 3380There is one category. Its objects are sequence spaces with their shifts; its morphisms are equivariant3381Markov kernels; sources are its states, channels its morphisms, codes its deterministic morphisms. It is3382monoidal, its hom-sets carry a divergence for which composition is short, and, taken up to almost sure3383equality, it has a dagger. Shannon's theory is the study of two numerical invariants of this category.3384Entropy measures a state by the smallest finite set of which its long blocks are approximate retracts;3385capacity measures a morphism by the largest finite set that is an approximate retract of its long blocks.3386The coding theorem says that a state can be pushed through a morphism when the first number is smaller3387than the second, because retractions compose, and cannot when it is larger, because both numbers are3388monotone.3389 3390That such invariants exist, are finite, and are given by the formulas $-\sum p\log p$ and $\max I$ is the3391content of the theory. The formula for entropy is forced by the chain rule, which is a cocycle condition.3392The existence of the limits is McMillan's theorem and Feinstein's lemma.3393 3394\section{What became formal}3395 3396The following statements, each of which costs Khinchin a computation, came out of general principles.3397 3398\begin{center}\small3399\renewcommand{\arraystretch}{1.25}3400\begin{tabular}{@{}p{0.43\textwidth}p{0.49\textwidth}@{}}3401\toprule3402\textbf{Statement} & \textbf{Mechanism}\\\midrule3403$H(AB)=H(A)+H_A(B)$ & functoriality of $H$ on $\FinProb$; the cocycle condition\\3404symmetry of entropy & commutativity of the monoid of observables\\3405uniqueness of entropy & $H^1(\Omega)\iso\R$, given the regularity theorem for the fundamental equation\\3406Shannon's inequality and its generalizations & positivity of relative entropy and the chain rule\\3407data processing & composition is short: the enrichment\\3408the compound source is stationary & morphisms of $\Dyn$ compose\\3409absence of anticipation & naturality between towers\\3410ergodic decomposition & disintegration over the invariant quotient\\3411convergence of conditional probabilities, in mean & monotone sequences of idempotents converge\\3412McMillan's theorem, in mean & chain rule, two idempotent limits, one tail estimate\\3413the second Shannon theorem & Fano's inequality: near-retractions lose little\\3414the converse & any monotone subadditive normalized function bounds the rate\\3415\bottomrule3416\end{tabular}3417\end{center}3418 3419\section{What did not}3420