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

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 4109\sol{12.4} Let $a_n$ be the number of allowed blocks of length $n$. An allowed block ends in $0$, preceded by4110any allowed block of length $n-1$, or in $01$, preceded by any allowed block of length $n-2$; so4111$a_n=a_{n-1}+a_{n-2}$ with $a_1=2$, $a_2=3$, and $a_n$ grows like $\phi^n$ with $\phi=\frac{1+\sqrt5}2$. A Markov chain4112with $q_{01}=a$ and $q_{10}=1$ has stationary distribution $(\frac1{1+a},\frac{a}{1+a})$ and entropy $\hb(a)/(1+a)$. Its4113derivative vanishes when $(1+a)\log\frac{1-a}{a}=\hb(a)$, that is, $(1-a)^2=a$, so $a=\frac{3-\sqrt5}2=\phi^{-2}$, and the4114maximum is $\log\phi$.4115 4116\sol{12.5} The entropies are $1$, $\log3\approx1.585$, $2$ and $2$. By \cref{thm:ornstein} and \cref{thm:KS}, one4117Bernoulli shift is a factor of another iff its entropy is not larger. So $B(\tfrac12,\tfrac12)$ is a factor of4118the other three, $B(\tfrac13,\tfrac13,\tfrac13)$ is a factor of Meshalkin's two, and those two are isomorphic. No4119other factor relations hold.4120%% ---- end sol/12.tex ----4121\backmatter4122%% ---- begin bib.tex ----4123\chapter{References}4124\begingroup\small4125\renewcommand{\chapter}[2]{}4126\begin{thebibliography}{FGLPS26}\setlength{\itemsep}{1pt}4127\newcommand{\bi}[1]{\bibitem[#1]{#1}}4128\bi{AC88} P. Algoet and T. Cover. A sandwich proof of the Shannon--McMillan--Breiman theorem. \emph{Ann. Probab.} 16 (1988).