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 3169–3268 of 4249. Source text is displayed literally.
3169probability under both. The \term{confusability graph} $G_W$ has vertex set $X$ and an edge between3170confusable inputs. A $(M,0)$-code is a set of $M$ pairwise non-confusable inputs, so3171$M^*(W,0)=\alpha(G_W)$, the independence number, and for $n$ uses3172$M^*(W^{\otimes n},0)=\alpha(G_W^{\boxtimes n})$, where $\boxtimes$ is the strong product of graphs.3173 3174\begin{definition}[Shannon]3175The \term{zero-error capacity} of $W$ is $C_0(W)=\lim_n\frac1n\log\alpha(G_W^{\boxtimes n})=\log\Theta(G_W)$.3176\end{definition}3177 3178\begin{example}\label{ex:pentagon}3179Let $X=Y=\Z/5$ and let $W$ send $x$ to $x$ or $x+1$ with probability $\tfrac12$ each. Its capacity is3180$\log5-1\approx1.322$. Its confusability graph is the pentagon $C_5$, with $\alpha(C_5)=2$, so one use carries one3181bit without error. But $\alpha(C_5\boxtimes C_5)=5$: the five words $(i,2i)$ are pairwise non-confusable. So3182two uses carry $\log5$ bits, and $C_0\ge\tfrac12\log5\approx1.161$.3183\end{example}3184 3185\begin{theorem}\label{thm:zeroerror}3186\Scl[\cite{Sha56,Lov79,Hae79,Alo98}] $\Theta(C_5)=\sqrt5$, so the bound in \cref{ex:pentagon} is the zero-error3187capacity. In general $\Theta$ is not multiplicative under the strong product and not additive under3188disjoint union: there are graphs with $\Theta(G\boxtimes H)>\Theta(G)\,\Theta(H)$ and with3189$\Theta(G\sqcup H)>\Theta(G)+\Theta(H)$. No algorithm is known that computes $\Theta$.3190\end{theorem}3191 3192Compare with \cref{prop:capacity}. Capacity is additive under tensor product, satisfies the sum formula of3193\cref{exer:sumchannel}, and is the solution of a convex optimization problem. Zero-error capacity has none of these3194properties. The exact rank of a stochastic matrix, in the sense of the largest identity that is a retract3195of it, does not become a homomorphism even after regularization.3196 3197\section{Asymptotic spectra}3198 3199Strassen found the right framework for regularized quantities of this kind while studying the complexity of3200matrix multiplication. Let $S$ be a commutative semiring containing the natural numbers, with a preorder3201$\le$ compatible with addition and multiplication, restricting to the usual order on $\N$, and such that3202every element is bounded by a natural number times any nonzero element. Define the \term{rank}3203$R(a)=\min\{n\in\N:a\le n\}$ and the \term{subrank} $Q(a)=\max\{n\in\N:n\le a\}$, and their regularizations3204$\tilde R(a)=\lim_nR(a^n)^{1/n}$ and $\tilde Q(a)=\lim_nQ(a^n)^{1/n}$. The \term{asymptotic spectrum} $\mathbf{X}(S)$ is3205the set of monotone semiring homomorphisms $S\to\R_{\ge0}$.3206 3207\begin{theorem}[Strassen]\label{thm:strassen}3208\Sli[\cite{Str88}] $\mathbf{X}(S)$ is a compact Hausdorff space, and for every $a\in S$,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 be