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 3809–3908 of 4249. Source text is displayed literally.
3809composite $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 ----3881%% ---- begin sol/05.tex ----3882\section*{Chapter 5}3883 3884\sol{5.1} $\pi=(b,a)/(a+b)$ and \cref{prop:markov} give the formula. It is a weighted average of $\hb(a)$ and3885$\hb(b)$, so it is at most $1$, with equality iff $a=b=\tfrac12$. It equals the entropy of the marginal iff the3886letters are independent, that is, iff the two rows of $Q$ agree: $a+b=1$.3887 3888\sol{5.2} An output block of length $n$ is a function of an input block of length $n+1$, so3889$H_n(\phi\circ\mu)\le H_{n+1}(\mu)$; divide by $n$. For independent fair bits the outputs $x_n+x_{n+1}$ are again3890independent fair bits, so both entropies are $1$. But $\phi$ is not an isomorphism: it identifies $x$ with3891its complement, and complementation preserves $\mu$, so $\phi$ is two-to-one almost everywhere. Equal entropy3892does not make a factor map invertible.3893 3894\sol{5.3} Given $g\colon X\to B$ put $\phi(x)_n=g(n\cdot x)$; conversely $g=\pi_0\circ\phi$. These are inverse3895bijections, as in \cref{prop:cofree}. Hence there are $|B|^{|A|^N}$ equivariant maps.3896 3897\sol{5.4} Given the past, $x_{n+1}$ has distribution $e_{\tau(x_n)}$, which depends on $x_n$ only. So the letters3898form a Markov chain with $q_{ab}=e_{\tau(a)}(b)$. The coalgebra is unifilar, and by \cref{prop:unifilar} its3899entropy is $\sum_s\sigma(s)H(e_s)=\sum_a\pi(a)H(q_{a\,\cdot})$, where $\pi$ is the stationary distribution of the3900letters and $\sigma=\tau_*\pi$. Conversely, given $Q$ take $S=A$, $\tau=\id$ and $e_a=q_{a\,\cdot}$.3901 3902\sol{5.5} Upper bound: $H(\mu)=\lim c_n$ and $c_n$ is nonincreasing (\cref{prop:rate}). Lower bound: for3903every $m$,3904\[ c_{n+m}\ \ge\ H(x_{n+m}\st x_0,\dots,x_{n+m-1},s_m)=H(x_{n+m}\st x_m,\dots,x_{n+m-1},s_m), \]3905because given $s_m$ the letters before time $m$ are independent of those after. By stationarity the right3906side is $H(x_n\st x_0,\dots,x_{n-1},s_0)$; let $m\to\infty$. Monotonicity of the lower bound: conditioning3907also on $s_1$ and then discarding $x_0,s_0$, which are independent of the future given $s_1$,3908$H(x_{n+1}\st x_0,\dots,x_n,s_0)\ge H(x_{n+1}\st x_1,\dots,x_n,s_1)$, and the right side is the bound for $n$.