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 3981–4080 of 4249. Source text is displayed literally.
3981$\tfrac12\,2^{-2n\varepsilon}$ and $2^{2n\varepsilon}$.3982 3983\sol{8.4} Order the blocks by decreasing probability, which is by increasing number of ones. By3984Exercise~6.4 the blocks with about $0.1n$ ones carry probability close to $\tfrac12$ in total and each has3985probability about $\tfrac12\,2^{-n\hb(0.1)}$; there are about $2^{n\hb(0.1)}$ of them. If $\lambda<\tfrac12$ they3986suffice. If $\lambda>\tfrac12$ one must add blocks from the second component, which have probability about3987$\tfrac12\,2^{-n}$ each, and a fixed positive fraction of all $2^n$ blocks is needed.3988 3989\sol{8.5} The probability of a block decreases with its number of ones, so an optimal set consists of all3990blocks with fewer than $k$ ones and some with exactly $k$, where $k=np+\Phi^{-1}(\lambda)\sqrt{np(1-p)}+o(\sqrt n)$ by3991the central limit theorem. The number of such blocks is $2^{n\hb(k/n)+O(\log n)}$, and3992$\hb(k/n)=\hb(p)+\hb'(p)(k/n-p)+O(1/n)$ with $\hb'(p)=\log\frac{1-p}{p}$. For $p=0.2$, $\sigma=0.8$; at $n=1000$ the3993correction for $\lambda=0.9$ is $0.8\cdot1.2816/\sqrt{1000}\approx0.032$, predicting $0.754$ against the computed3994$0.748$, and for $\lambda=0.1$ predicting $0.690$ against $0.683$. The remaining difference is the term of order3995$(\log n)/n$.3996%% ---- end sol/08.tex ----3997%% ---- begin sol/09.tex ----3998\section*{Chapter 9}3999 4000\sol{9.1} Erasure: the output reveals whether an erasure occurred, so $H(Y)=\hb(e)+(1-e)H(p)$ and4001$H(Y\st X)=\hb(e)$; $I=(1-e)H(p)$, maximal at the uniform input. Z-channel: with $q=\Prob(X=1)$,4002$I=\hb(q(1-\delta))-q\,\hb(\delta)$. Setting the derivative to zero, $(1-\delta)\log\frac{1-s}{s}=\hb(\delta)$ with $s=q(1-\delta)$, so4003$s=1/(1+2^{\hb(\delta)/(1-\delta)})$. Substituting, $I=-\log(1-s)=\log\bigl(1+2^{-\hb(\delta)/(1-\delta)}\bigr)$, and4004$2^{-\hb(\delta)/(1-\delta)}=(1-\delta)\,\delta^{\delta/(1-\delta)}$.4005 4006\sol{9.2} The output differs from the input iff exactly one of the two channels flips. For4007$\delta_1=\delta_2=0.1$ the flip probability is $0.18$ and $C=1-\hb(0.18)\approx0.320$, less than $0.531$.4008 4009\sol{9.3} The output blocks take two values, so $H_n(\eta)=1$ and $H(\eta)=0$. Since $\omega=\mu\otimes\eta$,4010$H_n(\omega)=H_n(\mu)+1$ and $H(\omega)=H(\mu)$. Hence $R(\mu,\nu)=0$, as it must be for a channel that ignores its input.4011 4012\sol{9.4} For inputs $(X,X')$ to the product channel, $Y$ and $Y'$ are conditionally independent given4013$(X,X')$ with $H(YY'\st XX')=H(Y\st X)+H(Y'\st X')$, and $H(YY')\le H(Y)+H(Y')$; so4014$I(XX';YY')\le I(X;Y)+I(X';Y')\le C(W)+C(W')$. Independent optimal inputs attain the bound. For the sum channel4015let $\lambda$ be the probability of using the first component. The output determines the component, so4016$I=\hb(\lambda)+\lambda I_1+(1-\lambda)I_2$, maximal over the conditional inputs at $\hb(\lambda)+\lambda C+(1-\lambda)C'$ and then over4017$\lambda$ at $\lambda=2^C/(2^C+2^{C'})$, with value $\log(2^C+2^{C'})$.4018 4019\sol{9.5} Naturality for maps says that the first $n$ letters of $\nu_{n+1}(x_1\dots x_{n+1})$ are4020$\nu_n(x_1\dots x_n)$, so the $n$-th output letter is a function $f_n$ of $x_1,\dots,x_n$, and any such sequence of4021functions is natural. For $y_n=x_{n+1}$ the law of $y_1$ depends on $x_2$ and is not a function of $x_1$.4022%% ---- end sol/09.tex ----4023%% ---- begin sol/10.tex ----4024\section*{Chapter 10}4025 4026\sol{10.1} On $E_x$ we have $Q(y)<W(y\st x)\,2^{-\gamma}/M$. Summing over $y\in E_x$ gives4027$Q(E_x)\le W(E_x\st x)\,2^{-\gamma}/M\le2^{-\gamma}/M$.4028 4029\sol{10.2} With uniform inputs the output is uniform, $Q(y)=2^{-n}$, and $W(y\st x)=\delta^d(1-\delta)^{n-d}$. Since4030$\delta<\tfrac12$ the density decreases in $d$ and $E_x$ is a ball. For $n=7$, $\delta=0.01$: $i=6.898$ at $d=0$ and4031$0.269$ at $d=1$. With $\log M=4$ and $\gamma>0$ the threshold $4+\gamma$ exceeds $0.269$, so $E_x=\{x\}$ and one needs4032$\gamma<2.898$. The guaranteed error is then $\Prob[d\ge1]+2^{-\gamma}$, with infimum4033$(1-0.99^7)+2^{-2.898}\approx0.068+0.134=0.202$. The Hamming code corrects one error and fails with probability4034$1-0.99^7-7(0.01)(0.99)^6\approx0.0020$. The lemma is sharp in rate and far from sharp at length seven.4035 4036\sol{10.3} Identity: $W(D_j\st x_j)\ge1-\varepsilon>0$ forces $x_j\in D_j$, and the sets are disjoint, so the codewords4037are distinct and $M^*=k$ for every $\varepsilon<1$. Constant channel with output law $Q$: one needs disjoint sets of4038$Q$-measure at least $1-\varepsilon$, so $M^*\le\lfloor1/(1-\varepsilon)\rfloor$, with $M^*=1$ for4039$\varepsilon<\tfrac12$. In both cases the answer agrees with capacity $\log k$ and $0$ after taking4040$\frac1n\log$ of the value for the $n$-th power.4041 4042\sol{10.4} With a stochastic encoder the $j$-th diagonal entry is $\sum_xe(x\st j)\,W(D_j\st x)\le\max_xW(D_j\st x)$, so4043replacing $e(\,\cdot\st j)$ by a maximizing $x$ does not decrease it. For the second part let $Y$ be a point4044and $M=2$. A deterministic decoder sends the point to one message and has maximal error $1$; a decoder that4045tosses a fair coin has maximal error $\tfrac12$.4046 4047\sol{10.5} If the unerased positions distinguish $x_j$ from every other codeword, the decoder returns $x_j$.4048For a linear code with a $k\times n$ generator matrix $G$ and erased set $S$, this happens for every codeword4049iff the columns of $G$ outside $S$ have rank $k$, so the error probability is the same for all codewords.4050Choose $G$ uniformly at random. For a fixed nonzero message $v$ the vector $vG$ restricted to the $n-|S|$4051unerased positions is uniform, so it vanishes with probability $2^{-(n-|S|)}$, and the union bound gives4052failure probability at most $2^{k-n+|S|}$ given $S$. With probability tending to one $|S|\le n(e+\delta)$, so the4053expected failure probability is at most $2^{k-n(1-e-\delta)}+o(1)$, which is small when $k/n<1-e-2\delta$. Some $G$4054does at least as well as the average.4055%% ---- end sol/10.tex ----4056%% ---- begin sol/11.tex ----4057\section*{Chapter 11}4058 4059\sol{11.1} Huffman's procedure merges $0.1$ and $0.2$, then the result with $0.3$, then with $0.4$, giving4060lengths $(1,2,3,3)$ and codewords $0,10,110,111$. The expected length is $0.4+0.6+0.6+0.3=1.9$ and4061$H(p)\approx1.846$.4062 4063\sol{11.2} In the proof of \cref{thm:noiseless}, $L-H(p)=\KL pq-\log K$ with both terms nonnegative. Equality4064needs $K=1$ and $p=q$, so $p(x)=2^{-\ell(x)}$. Conversely if every $p(x)$ is a power of $\tfrac12$ the lengths4065$-\log p(x)$ satisfy Kraft's inequality with equality.4066 4067\sol{11.3} Let the channel code have $M$ messages, of which message $1$ is always decoded wrongly and the4068others always correctly; its average error is $1/M$. Let the compression send a set of source blocks of4069probability $0.9$ to message $1$. The composite fails with probability at least $0.9$. Repair: discard the4070worse half of the messages. If the average error is $\varepsilon$, at most half of the messages have error above4071$2\varepsilon$, so the remaining $M/2$ form a code with maximal error $2\varepsilon$, at a cost of one bit.4072 4073\sol{11.4} If $f$ factors through $[r]$ so does every composite with $f$, which gives (i); if $f,g$ factor4074through $[r],[s]$ then $f\otimes g$ factors through $[rs]$, which gives (ii). For (iii), if $f\colon[M]\to[M]$ has4075diagonal at least $1-\varepsilon$ and factors through $[r]$, then4076$(1-\varepsilon)\log M-1\le C(f)\le\log r$ by Fano's inequality and \cref{prop:capacity}(iv). The bound is4077$\frac1n\log M^*(W^{\otimes n},\varepsilon)\le(\log r_+(W)+\frac1n)/(1-\varepsilon)$. For a binary symmetric channel with4078$0<\delta<\tfrac12$, $r_+=2$ and $\Phi=1>1-\hb(\delta)$. The function $\log\min\{|X|,|Y|\}$ fails (i): a composite4079$X\to1\to X$ has $\Phi=\log|X|$ while each factor has $\Phi=0$.4080