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 3221–3320 of 4249. Source text is displayed literally.
3221 3222So zero-error capacity is the minimum of a family of additive, multiplicative, monotone invariants, each3223of which is individually as well behaved as capacity. The family is a compact space of which only some3224points are known. This is the structure that the tolerance $\varepsilon$ removes.3225 3226\section{Sources: the R\'enyi family}3227 3228The same phenomenon appears on the source side, in a form that can be computed completely. Recall the3229R\'enyi entropies $H_\alpha$ of \cref{ch:uniqueness}, with $H_0(p)=\log|\supp p|$ and $H_1=H$.3230 3231\begin{theorem}[Exact, exponential and constant error]\label{thm:exponent}3232\Scl[\cite{CK11}] Let $p$ be a distribution on a finite set and consider compressions of $p^{\otimes n}$ in the3233sense of \cref{def:compression}.3234\begin{enumerate}[label=(\roman*)]3235\item With no error, $M_*(p^{\otimes n},0)=|\supp p|^n$: the rate is $H_0(p)$.3236\item With error at most a fixed $\varepsilon\in(0,1)$, the rate is $H_1(p)=H(p)$.3237\item With error required to be at most $2^{-nr}$, a rate $R$ strictly between $H(p)$ and $H_0(p)$ is3238achievable iff3239\[ r\le\sup_{\rho\ge0}\rho\,\bigl(R-H_{1/(1+\rho)}(p)\bigr). \]3240\end{enumerate}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$.