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

3181bit 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 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*)]