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 3289–3388 of 4249. Source text is displayed literally.
3289entropy $2$ and are isomorphic, as Meshalkin showed by an explicit code \cite{Mes59}.3290 3291Read these as statements about rank and subrank in the preorder of factor maps. By (i) and3292\cref{thm:KS}, the entropy of an ergodic source is the supremum of the entropies of its Bernoulli factors:3293a subrank, with Bernoulli shifts in the role of the finite sets $[M]$. By (iii) and \cref{thm:KS} again, it is3294the infimum of $\log k$ over the alphabets on which the source can be represented: a rank. The two agree,3295with no tolerance and no regularization. Krieger's theorem is the noiseless coding theorem in this3296setting, and Sinai's theorem says that from any ergodic source one can extract fair bits at the rate of3297its entropy. The finite theorems of \cref{ch:aep,ch:shannon} are approximations to these, in which the3298infinite delay of a general stationary code is replaced by blocks of length $n$ and the price is the3299tolerance.3300 3301\section{Channels without noise}3302 3303Shannon's 1948 paper begins with a channel that makes no errors but restricts which sequences may be sent.3304If the allowed sequences are the paths in a finite directed graph with adjacency matrix $\mathsf{A}$, the3305number of allowed blocks of length $n$ grows like $\lambda^n$, where $\lambda$ is the largest eigenvalue of3306$\mathsf{A}$, and the capacity is $\log\lambda$.3307 3308\begin{theorem}\label{thm:parry}3309\Scl[\cite{Sha48,Par64}] For an irreducible graph, $\log\lambda$ is the maximum of $H(\mu)$ over stationary3310sources supported on allowed sequences, and the maximum is attained by a unique Markov source.3311\end{theorem}3312 3313In dynamics $\log\lambda$ is the topological entropy of the shift of finite type and the theorem is the3314variational principle for it. Here the exact count and the approximate one agree because the channel is3315deterministic: with no noise, $\varepsilon$ has nothing to do.3316 3317\begin{example}\label{ex:golden}3318Forbid two consecutive ones. The number of allowed blocks of length $n$ is a Fibonacci number, and the3319capacity is $\log\frac{1+\sqrt5}{2}\approx0.694$. The maximizing source is the Markov chain that follows a $0$ by a3320$1$ with probability $\frac{3-\sqrt5}{2}\approx0.382$ and always follows a $1$ by a $0$.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.