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 3141–3240 of 4249. Source text is displayed literally.
3141\end{exercise}3142 3143\begin{exercise}3144Let $r_+(W)$ be the least size of a set through which $W$ factors in $\FinStoch$. Show that3145$\Phi=\log r_+$ satisfies the hypotheses of \cref{thm:universal}, state the bound it gives, and give a channel3146with $\Phi(W)>C(W)$. Does $\Phi(W)=\log\min\{|X|,|Y|\}$ satisfy the hypotheses?3147\end{exercise}3148 3149\begin{exercise}\label{exer:bec}3150For the erasure channel prove that $W^-$ and $W^+$ are erasure channels with probabilities $2e-e^2$ and3151$e^2$. Let $f(e)=\sqrt{e(1-e)}$. Show that $\tfrac12\bigl(f(2e-e^2)+f(e^2)\bigr)\le\tfrac{\sqrt3}{2}f(e)$, and deduce3152\cref{thm:polar} for erasure channels without any martingale theorem.3153\end{exercise}3154%% ---- end ch/11-shannon.tex ----3155%% ---- begin ch/12-rates.tex ----3156\chapter{Rates and Spectra}\label{ch:rates}3157 3158Entropy and capacity were obtained in the last chapters as limits: growth rates of the sizes of sets that3159are approximate retracts of, or admit approximate retractions onto, tensor powers. Two features of the3160definitions did the work, the tolerance $\varepsilon$ and the passage to the limit. This chapter asks what3161each contributes. Without the tolerance, the limits still exist but are governed by a family of invariants3162and not by one number. Strassen's theory of asymptotic spectra describes such families. In the infinite3163setting of ergodic theory, on the other hand, the tolerance is not needed at all. None of this is in3164Khinchin; it is the context in which his theorems now sit.3165 3166\section{Coding without error}3167 3168Let $W\colon X\to Y$ be a stochastic matrix. Two inputs are \term{confusable} if some output has positive3169probability 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}