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 4009–4108 of 4249. Source text is displayed literally.
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 4081\sol{11.5} $W^-$: the decoder sees $y_1,y_2$ and wants $u_1=x_1\oplus x_2$, which is known iff neither output is4082erased; the erasure probability is $1-(1-e)^2$. $W^+$: given $u_1$, the bit $u_2$ equals $x_2$ and equals4083$x_1\oplus u_1$, so it is unknown iff both outputs are erased, with probability $e^2$. Next,4084$f(2e-e^2)=f(e)\sqrt{(2-e)(1-e)}$ and $f(e^2)=f(e)\sqrt{e(1+e)}$, and by the Cauchy--Schwarz inequality4085$\sqrt{(2-e)(1-e)}+\sqrt{e(1+e)}\le\sqrt{(2-e)+(1+e)}\,\sqrt{(1-e)+e}=\sqrt3$. Hence the average of $f(e_b)$ over4086the $2^n$ channels is at most $(\tfrac{\sqrt3}{2})^n f(e)$, and by Markov's inequality the fraction with4087$e_b\in[\delta,1-\delta]$, where $f\ge\sqrt{\delta(1-\delta)}$, tends to zero geometrically. The mean of $e_b$ is4088conserved, so the fraction with $e_b<\delta$ tends to $1-e$.4089%% ---- end sol/11.tex ----4090%% ---- begin sol/12.tex ----4091\section*{Chapter 12}4092 4093\sol{12.1} In $C_5$ any three vertices contain two adjacent ones, and $\{0,2\}$ is independent. Two words4094$(i,2i)$ and $(j,2j)$ with $i\ne j$ are confusable only if $i-j\in\{0,\pm1\}$ and $2(i-j)\in\{0,\pm1\}$ modulo4095$5$; for $i-j=\pm1$ the second difference is $\pm2$. For the capacity, $H(Y\st X)=1$ for every input and4096the uniform input gives the uniform output, so $C=\log5-1$.4097 4098\sol{12.2} For $0<\alpha<1$ the function $t\mapsto t^\alpha$ is concave, so $\sum_iq_i^\alpha=\sum_i(\sum_jD_{ij}p_j)^\alpha\ge\sum_{i,j}D_{ij}p_j^\alpha=\sum_jp_j^\alpha$,4099and $H_\alpha=\frac1{1-\alpha}\log\sum p^\alpha$ increases. For $\alpha>1$ the inequality reverses and so does the sign of4100$1-\alpha$. The cases $\alpha=0,1,\infty$ follow by continuity, or directly. Then use additivity:4101$H_\alpha(p^{\otimes n})=nH_\alpha(p)$.4102 4103\sol{12.3} (i) Every block in the support has positive probability, so $d\circ e$ must be the identity on all4104$|\supp p|^n$ of them, and conversely that many messages suffice. For the numbers: $\hb(\tau)=0.7$ gives4105$\tau\approx0.1893$, and $\KL{(1-\tau,\tau)}{p}\approx0.0521$. The supremum of $\rho(0.7-H_{1/(1+\rho)}(p))$ is attained near4106$\rho\approx0.51$ and is also $0.0521$. The first expression is the exponent of the probability that a block has4107more than $\tau n$ ones, which is the event that the best set of $2^{nR}$ blocks misses it.4108