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 3761–3860 of 4249. Source text is displayed literally.
3761outside the reach of a finite computation.3762%% ---- end ch/C-computations.tex ----3763%% ---- begin ch/D-solutions.tex ----3764\chapter{Solutions to the Exercises}\label{app:solutions}3765 3766Solutions are given for every exercise, numbered as in the chapters. Where an exercise asks for a3767computation, the numbers below are recomputed by the script of \cref{app:computations}.3768%% ---- end ch/D-solutions.tex ----3769%% ---- begin sol/01.tex ----3770\section*{Chapter 1}3771 3772\sol{1.1} $g$ has image $(\tfrac34,\tfrac18,\tfrac18)$ and one nontrivial fibre, of mass $\tfrac34$ and conditional3773distribution $(\tfrac23,\tfrac13)$: $H(g)=\tfrac34\hb(\tfrac23)\approx0.689$. Then $h$ has image3774$(\tfrac34,\tfrac14)$ and one nontrivial fibre of mass $\tfrac14$ and conditional distribution3775$(\tfrac12,\tfrac12)$: $H(h)=0.25$. The composite has $H(h\circ g)=H(p)-\hb(\tfrac14)\approx1.75-0.811=0.939$, the3776sum of the two.3777 3778\sol{1.2} $H(f)=H(p)-H(f_*p)$ and $H(f_*p)=0$ iff $f_*p$ is a point mass. If $f$ is an isomorphism then3779$H(f)=0$ since $f$ is injective, so $H(p)=H(q)$. The converse fails: $(\tfrac12,\tfrac14,\tfrac18,\tfrac18)$3780and $(a,a,b,b,b,b)$ with $2a+4b=1$ can be given the same entropy $1.75$ by the intermediate value theorem3781($a=b=\tfrac16$ gives $\log6\approx2.58$ and $a\to\tfrac12$ gives $1$), and they are not isomorphic.3782 3783\sol{1.3} By \cref{prop:chainrule}, $p=(t,1-t)\circ(u_1,p')$ where $p'$ is the conditional distribution on the3784other $n-1$ points, so $H(p)=\hb(t)+(1-t)H(p')\le\hb(t)+(1-t)\log(n-1)$ by \cref{prop:properties}(ii).3785 3786\sol{1.4} If $W=\sum_k\lambda_k\Pi_k$ with permutation matrices $\Pi_k$, concavity of $H$ gives3787$H(Wp)\ge\sum_k\lambda_kH(\Pi_kp)=H(p)$. Conversely apply the hypothesis to the uniform state $u$:3788$H(Wu)\ge\log|X|$ forces $Wu=u$ by \cref{prop:properties}(ii), which says that the rows of the matrix of $W$3789(indexed by outputs) sum to one. Its columns sum to one because it is stochastic.3790 3791\sol{1.5} $H(X\st Z)\le H(X,Y\st Z)=H(Y\st Z)+H(X\st Y,Z)$, and $H(X\st Y,Z)=H(X\st Y)$ because $X$ and $Z$ are3792conditionally independent given $Y$. If both kernels are maps, $Y$ is a function of $X$ and $Z$ a function3793of $Y$, so $H(X,Y\st Z)=H(X\st Z)$. For strict inequality take $X$ and $Y$ independent fair bits and $Z$ a point:3794$H(X\st Z)=1<H(X\st Y)+H(Y\st Z)=2$.3795%% ---- end sol/01.tex ----3796%% ---- begin sol/02.tex ----3797\section*{Chapter 2}3798 3799\sol{2.1} Here $g=6$ and $(g_1,g_2,g_3)=(3,2,1)$. $Y$ has six points in blocks of sizes $3,2,1$, and $r$ puts3800mass $\tfrac16$ on each pair $(i,y)$ with $y$ in block $i$. Then $\log6-\tfrac12\log3-\tfrac13\log2\approx2.585-0.792-0.333=1.459$, and3801$H(p)=\tfrac12\cdot1+\tfrac13\log3+\tfrac16\log6\approx0.5+0.528+0.431=1.459$.3802 3803\sol{2.2} By symmetry it is enough to treat $i=n$. For $k=1$ there is nothing to prove, and $k=2$ is3804recursivity. Let $q\in\Delta_k$ with $k\ge3$ and put $s=q_{k-1}+q_k$. If $s=0$ use expansibility, which is3805recursivity with $q_2=0$. Otherwise let $q'=(q_1,\dots,q_{k-2},s)$. Recursivity applied to $p\circ_nq$, whose3806last two entries are $p_nq_{k-1}$ and $p_nq_k$, gives3807$H(p\circ_nq)=H(p\circ_nq')+p_ns\,H(\tfrac{q_{k-1}}{s},\tfrac{q_k}{s})$. By induction $H(p\circ_nq')=H(p)+p_nH(q')$,3808and recursivity for $q$ itself gives $H(q)=H(q')+sH(\tfrac{q_{k-1}}{s},\tfrac{q_k}{s})$. Combine. The full3809composite $q\circ(p_1,\dots,p_m)$ is obtained by $m$ partial composites, the $i$-th of which contributes3810$q_iH(p_i)$.3811 3812\sol{2.3} $\sum_{i,j}(p_iq_j)^\alpha=\sum_ip_i^\alpha\sum_jq_j^\alpha$ gives additivity. Adding a zero does not3813change $\sum p_i^\alpha$. For $\alpha<1$ the function $t^\alpha$ is concave, so $\sum_ip_i^\alpha\le n^{1-\alpha}$ and3814$H_\alpha\le\log n$; for $\alpha>1$ it is convex, the inequality reverses, and so does the sign of $1-\alpha$.3815By l'H\^opital's rule, $\lim_{\alpha\to1}H_\alpha(p)=-\frac{d}{d\alpha}\log\sum_ip_i^\alpha\big|_{\alpha=1}=-\sum_ip_i\log p_i$.3816 3817\sol{2.4} Continuity is clear. A map $f$ sends $p$ to a distribution $q$ obtained by adding entries, and3818$(a+b)^2\ge a^2+b^2$, so $\sum q^2\ge\sum p^2$ and $H_2(q)\le H_2(p)$. Let $f\colon(2,u_2)\to1$ and $f'=\id_1$.3819Then $\tfrac12f\oplus\tfrac12f'$ maps $(\tfrac14,\tfrac14,\tfrac12)$ to $(\tfrac12,\tfrac12)$ and has3820$F=\log\tfrac83-1\approx0.415$, whereas $\tfrac12F(f)+\tfrac12F(f')=0.5$. In the proof, functoriality still gives3821$F(f)=I(p)-I(q)$; what fails is the identity $F(f)=\sum_iq_iI(p_i)$, that is, the chain rule.3822 3823\sol{2.5} $u_1\circ_1u_1=u_1$ gives $I(u_1)=I(u_1)+I(u_1)$. Next $(1,0)\circ_1(1,0)=(1,0,0)=(1,0)\circ_2(1,0)$3824gives $I(1,0)+1\cdot I(1,0)=I(1,0)+0\cdot I(1,0)$, so $I(1,0)=0$. For the chain rule write3825$q\circ(p_1,\dots,p_m)=(\cdots((q\circ_mp_m)\circ_{m-1}p_{m-1})\cdots)\circ_1p_1$. Inserting at position $i$ does3826not change the entries at positions before $i$, so the $i$-th step adds $q_iI(p_i)$.3827%% ---- end sol/02.tex ----3828%% ---- begin sol/03.tex ----3829\section*{Chapter 3}3830 3831\sol{3.1} As in \cref{lem:action}, the weight of the block $B\cap C$ in $Y._\alpha(Z._\alpha f)$ is3832$P(B)^\alpha\bigl(P(B\cap C)/P(B)\bigr)^\alpha=P(B\cap C)^\alpha$. And $Y._\alpha1=\sum_BP(B)^\alpha$, which equals $1$ for all3833$P$ and $Y$ iff $\alpha=1$.3834 3835\sol{3.2} Write $s_Y=\sum_BP(B)^\alpha$. Then3836$Y._\alpha S_\alpha[Z]=\frac1{\alpha-1}\sum_BP(B)^\alpha\bigl(1-\sum_C(P(B\cap C)/P(B))^\alpha\bigr)=\frac{1}{\alpha-1}(s_Y-s_{YZ})$, and3837adding $S_\alpha[Y]=\frac1{\alpha-1}(1-s_Y)$ gives $\frac1{\alpha-1}(1-s_{YZ})$. If $Y$ and $Z$ are independent,3838$s_{YZ}=s_Ys_Z$ and $s=1-(\alpha-1)S_\alpha$; substitute.3839 3840\sol{3.3} The observables are $1$ and the atomic partition $X$. A 1-cochain is a pair $(f[1],f[X])$ with3841$f[1]$ a constant and $f[X]$ a measurable function $h$ of $P(a)\in[0,1]$. The cocycle conditions for the four3842pairs reduce to $f[1]=0$ and $X.f[X]=0$, that is, $P(a)h(1)+P(b)h(0)=0$ for all $P$. So $Z^1$ is the space of3843measurable $h$ with $h(0)=h(1)=0$, there are no coboundaries, and $H^1$ is that infinite-dimensional space.3844 3845\sol{3.4} For $h(x)=x$ both sides equal $x+y$. For $\hb$, splitting off the first outcome of $(x,y,1-x-y)$3846gives $\hb(x)+(1-x)\hb(\frac{y}{1-x})$ by \cref{prop:chainrule}, and splitting off the second gives the other3847side. There is no contradiction, because a cocycle vanishes at deterministic laws (Step~0), which forces3848$h(1)=0$.3849 3850\sol{3.5} $ab-a^pb^p=(a-a^p)\,b+a^p\,(b-b^p)$; divide by $p$ and use $a^p\equiv a$. Next3851$H_5(2,4)=(1-32-1024)/5=-211\equiv4$, and $\sum_{k=1}^4 2^k/k=2+2+8\cdot3^{-1}+4$ with $3^{-1}=2$ in3852$\mathbb{F}_5$, giving $9\equiv4$. In $\mathbb{F}_3$: $H_3(2,2)=(1-8-8)/3=-5\equiv1$ and3853$H_3(1,1,2)=(1-1-1-8)/3=-3\equiv0$. The chain rule predicts3854$H_3(2,2)+2\cdot H_3(2,2)+2\cdot H_3(1)=1+2+0\equiv0$.3855%% ---- end sol/03.tex ----3856%% ---- begin sol/04.tex ----3857\section*{Chapter 4}3858 3859\sol{4.1} $\KL pq=\tfrac12\log2+\tfrac12\log\tfrac23\approx0.2075$ and3860$\KL qp=\tfrac14\log\tfrac12+\tfrac34\log\tfrac32\approx0.1887$. The channel fixes $p$ and sends $q$ to