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

3209\[ \tilde Q(a)=\min_{\phi\in\mathbf{X}(S)}\phi(a),\qquad\tilde R(a)=\max_{\phi\in\mathbf{X}(S)}\phi(a). \]3210Moreover $a^n\le b^{n+o(n)}$ for large $n$ iff $\phi(a)\le\phi(b)$ for all $\phi\in\mathbf{X}(S)$.3211\end{theorem}3212 3213\begin{theorem}[Zuiddam]\label{thm:zuiddam}3214\Sli[\cite{Zui19}] Finite graphs, with disjoint union as sum, strong product as product, and the preorder3215in which $G\le H$ when there is a homomorphism from the complement of $G$ to the complement of $H$, form3216such a semiring. Its subrank is the independence number, and therefore3217\[ \Theta(G)=\min_{\phi\in\mathbf{X}(\mathrm{graphs})}\phi(G). \]3218The Lov\'asz theta function, the fractional clique cover number and the fractional Haemers bounds are3219points of the spectrum.3220\end{theorem}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}