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 3941–4040 of 4249. Source text is displayed literally.
3941 3942\sol{7.1} $e_\GG(y\st x)=\tfrac12$ if $x,y\in\{1,2\}$, $\tfrac14$ if $x,y\in\{3,4,5,6\}$, and $0$ otherwise. It is3943block diagonal with blocks $\tfrac12J_2$ and $\tfrac14J_4$, where $J_k$ is the all-ones matrix; these are symmetric3944and idempotent. On $f(x)=x$ it gives the block averages: $1.5$ on $\{1,2\}$ and $4.5$ on $\{3,4,5,6\}$.3945 3946\sol{7.2} If $\GG\subseteq\GG'$, resampling given $\GG'$ and then given $\GG$ is resampling given $\GG$, and in the3947other order the second step does not change the $\GG$-class; so both composites are $e_\GG$. Conversely if3948$e_\GG e_{\GG'}=e_\GG$ then every $\GG$-measurable $g$ satisfies $\E[g\st\GG']=g$ after applying $L^2$ and taking3949adjoints, so it is $\GG'$-measurable. On $\{1,2,3\}$ with the uniform distribution take the partitions3950$\{1,2\}|\{3\}$ and $\{1\}|\{2,3\}$. The function $f=1_{\{1\}}$ is sent by the first projection to3951$(\tfrac12,\tfrac12,0)$ and then by the second to $(\tfrac12,\tfrac14,\tfrac14)$; in the other order it is3952fixed by the second and sent to $(\tfrac12,\tfrac12,0)$ by the first.3953 3954\sol{7.3} $\E[f\st\FF_n]$ is the midpoint of the dyadic interval containing $x$. On each interval $f$ minus3955the midpoint is uniform on an interval of length $2^{-n}$ centred at $0$, with variance $2^{-2n}/12$.3956 3957\sol{7.4} The factors are independent with mean $\tfrac12(1.6+0.4)=1$, so $M_n$ is a martingale with mean3958$1$, and $\E\sqrt{M_n}=(\tfrac12(\sqrt{1.6}+\sqrt{0.4}))^n=\rho^n$. By Markov's inequality3959$\Prob(M_n>\delta)\le\rho^n/\sqrt\delta\to0$. If $M_n=\E[f\st\FF_n]$ then $M_n\to f$ in $L^1$ by \cref{cor:levy}, so $f=0$,3960contradicting $\E M_n=1$.3961 3962\sol{7.5} $\sigma$ has order $6$, so $\frac16\sum_{k<6}U^k$ averages a function over the orbits of $\sigma$: it is block3963diagonal with blocks $\tfrac13J_3$ and $\tfrac12J_2$. This is the conditional expectation, for the uniform3964distribution, onto the $\sigma$-algebra generated by the cycles, which is the invariant $\sigma$-algebra.3965%% ---- end sol/07.tex ----3966%% ---- begin sol/08.tex ----3967\section*{Chapter 8}3968 3969\sol{8.1} $i_n=\sum_{k<n}-\log p(x_k)$ is a sum of independent identically distributed terms with mean $H$ and3970variance $\sigma^2$, so $\frac1ni_n$ has variance $\sigma^2/n$. For a bit with $\Prob(1)=p$ the term takes two values3971differing by $\log\frac{1-p}{p}$, so $\sigma^2=p(1-p)\log^2\frac{1-p}{p}$; at $p=0.2$ this is $0.16\cdot4=0.64$.3972 3973\sol{8.2} By the Markov property $\mu(x_0\st x_{-k},\dots,x_{-1})=q_{x_{-1}x_0}$ for $k\ge1$. So3974$i_n=g_0+\sum_{k=1}^{n-1}g_1\circ T^k$ with $g_1$ bounded on the support of $\mu$, and3975$\frac1ni_n\to\E[g_1\st\II]$ in $L^1$, which is $\E g_1=H(\mu)$ if the source is ergodic.3976 3977\sol{8.3} Each block of $T_n^\varepsilon$ has probability at least $2^{-n(H+\varepsilon)}$ and the total is at most $1$;3978each has probability at most $2^{-n(H-\varepsilon)}$ and the total is at least $1-\delta$. For \cref{prop:uniform}3979take $S=T_n^\varepsilon$ with $n$ so large that $\mu_n(S)\ge1-\varepsilon\ge\tfrac12$. Then3980$\tfrac12\,2^{n(H-\varepsilon)}\le|S|\le2^{n(H+\varepsilon)}$, and $\mu_n(C)|S|$ lies between3981$\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.