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

3241\end{theorem}3242 3243As the required exponent $r$ goes from $0$ to $\infty$ the relevant order $\alpha=1/(1+\rho)$ goes from $1$3244to $0$. Each $H_\alpha$ with $0\le\alpha\le1$ is additive under tensor product and monotone under mixing3245(\cref{exer:schur}), so each gives an obstruction of the kind in \cref{thm:universal}; which of them is3246binding depends on how small the error must be. For transformations between distributions under3247majorization, which is the same as the theory of bipartite pure quantum states under local operations,3248Jensen and Vrana showed that the asymptotic spectrum is exactly the family of power sums3249$p\mapsto\sum_ip_i^\alpha$ with $0\le\alpha\le1$, and expressed optimal rates as infima over it3250\cite{JV20}; see also \cite{Fri17,Kli07,Tur07}.3251 3252The role of the tolerance can now be stated precisely.3253 3254\begin{proposition}[Collapse]\label{prop:collapse}3255\Sob Let $\mu$ be an ergodic source and $\varepsilon>0$. For all large $n$ there is a set $S\subseteq A^n$ with3256$\mu_n(S)\ge1-\varepsilon$ such that the conditioned law $\mu_n|_S$ satisfies3257\[ \Bigl|\frac1nH_\alpha(\mu_n|_S)-H(\mu)\Bigr|\le4\varepsilon\qquad\text{for every }\alpha\in[0,\infty]. \]3258\end{proposition}3259 3260\begin{proof}3261Take $S$ as in \cref{prop:uniform}. The conditioned law has all its probabilities between3262$2^{-a}/|S|$ and $2^a/|S|$ with $a=n(2\varepsilon+\frac2n)$. Then3263$\log|S|-a\le H_\infty\le H_\alpha\le H_0=\log|S|$, and $\frac1n\log|S|$ is within $\varepsilon+\frac1n$ of $H(\mu)$.3264\end{proof}3265 3266Before conditioning, the R\'enyi rates of an ergodic source are in general all different. Discarding a3267set of probability $\varepsilon$ makes them equal. McMillan's theorem is the statement that the spectrum3268of a source, in the sense of this chapter, collapses to a point once sets of small probability may be3269ignored, and Shannon entropy is the value at that point. The analogue for channels is \cref{thm:rank}, with3270the strong converse: the many invariants of \cref{thm:zuiddam} are replaced by one.3271 3272\section{Infinite time: entropy as a rank}3273 3274In ergodic theory the objects are stationary sources, or more generally measure-preserving systems, and3275the morphisms are stationary codes. Let $B(p)$ be the source of independent letters with distribution3276$p$, a \term{Bernoulli shift}.3277 3278\begin{theorem}\label{thm:ornstein}3279\Scl[\cite{Sin64,Orn70,Kri70}]3280\begin{enumerate}[label=(\roman*)]3281\item (Sinai) If $\mu$ is ergodic and $H(p)\le H(\mu)$, then $B(p)$ is a factor of $\mu$.3282\item (Ornstein) $B(p)$ and $B(q)$ are isomorphic iff $H(p)=H(q)$.3283\item (Krieger) If $\mu$ is ergodic and $H(\mu)<\log k$, then $\mu$ is isomorphic to a stationary source on $k$3284letters.3285\end{enumerate}3286\end{theorem}3287 3288For instance $B(\tfrac14,\tfrac14,\tfrac14,\tfrac14)$ and $B(\tfrac12,\tfrac18,\tfrac18,\tfrac18,\tfrac18)$ both have3289entropy $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}.