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 3781–3880 of 4249. Source text is displayed literally.
3781($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$ to3861$(0.3,0.7)$, and $\KL{(\frac12,\frac12)}{(0.3,0.7)}=\tfrac12\log\tfrac{5}{3}+\tfrac12\log\tfrac57\approx0.1258<0.2075$.3862 3863\sol{4.2} Write $r(x,y)=p(x)r(y\st x)$ and $r'(x,y)=p'(x)r'(y\st x)$; then3864$\log\frac{r}{r'}=\log\frac{p}{p'}+\log\frac{r(y\st x)}{r'(y\st x)}$, and averaging against $r$ gives the formula. In the proof3865of \cref{thm:DPI} the only inequality is the positivity of3866$\sum_y(f\circ p)(y)\KL{r(\,\cdot\st y)}{r'(\,\cdot\st y)}$, which vanishes iff each term with $(f\circ p)(y)>0$ does.3867 3868\sol{4.3} $\TV=1-\sum p^2=1-\tfrac38=\tfrac58$ and $\KL{\cpy\circ p}{p\otimes p}=H(p)=1.5$. Both are largest at the uniform3869state, where they equal $1-\tfrac1n$ and $\log n$: the first because $\sum p^2\ge\tfrac1n$ by the3870Cauchy--Schwarz inequality, the second by \cref{prop:properties}(ii).3871 3872\sol{4.4} The marginals are uniform, so $I(X;Y)=1+1-H(0.4,0.4,0.1,0.1)=2-1.722=0.278$. A function of $X$ that3873is also a function of $Y$ takes the same value at $(0,0)$ and $(0,1)$, at $(0,1)$ and $(1,1)$, and so on;3874all four points have positive probability, so it is constant. For the second part take $Y=X$ a fair bit:3875$X\wedge Y=X$ and $I(X;Y)=H[X]=1$.3876 3877\sol{4.5} Given $Y=y$, the posterior of $X$ is $1-\varepsilon$ at $y$ and $\varepsilon/(n-1)$ elsewhere; since3878$\varepsilon<1-\tfrac1n$ the maximum is at $y$, so $P_e=\varepsilon$. By the equality case of Exercise~1.3,3879$H(X\st Y=y)=\hb(\varepsilon)+\varepsilon\log(n-1)$ for every $y$.3880%% ---- end sol/04.tex ----