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

3841$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$.3909Convergence: the gap between the bounds is $I(s_0;x_n\st x_0,\dots,x_{n-1})$, and these terms sum to at most3910$H(s_0)$.3911%% ---- end sol/05.tex ----3912%% ---- begin sol/06.tex ----3913\section*{Chapter 6}3914 3915\sol{6.1} A stationary distribution of $Q$ is a convex combination $\lambda\pi'+(1-\lambda)\pi''$ of the unique3916stationary distributions of the two classes, and the corresponding Markov source is the same combination of3917the two sources supported on sequences that stay in one class. Each of those is ergodic by3918\cref{prop:iid}. The event of lying in the first class is invariant with measure $\lambda$, so interior3919points are not ergodic. By \cref{prop:markov} the entropy is $\sum_a\pi(a)H(q_{a\,\cdot})$, which is linear in $\pi$.3920 3921\sol{6.2} If $\mu$ is ergodic, apply \cref{thm:birkhoff} to $f=1_{C'}$: $A_nf\to\mu(C')$ in $L^1$; multiply by $1_C$3922and integrate. Conversely the condition extends from cylinders to all measurable sets by approximation, and3923for an invariant $S$ it gives $\mu(S)=\mu(S\cap T^{-k}S)\to\mu(S)^2$.3924 3925\sol{6.3} The lower inequality is concavity of $H$ on $\Delta(A^n)$. For the upper one, let $J$ be the label of3926the component: $H_n(\mu)\le H(x_1\dots x_n,J)=H(J)+H(x_1\dots x_n\st J)$. Equality holds for all $n$ when the label3927is a function of every block, for instance when $\mu'$ and $\mu''$ are the two constant sequences on $\{0,1\}$:3928then $H_n(\mu)=\hb(\lambda)$ and $H_n(\mu')=H_n(\mu'')=0$.3929 3930\sol{6.4} Write $\mu_n=\tfrac12\mu'_n+\tfrac12\mu''_n$. On the first component the number of ones is $0.1n+o(n)$3931almost surely, so $-\frac1n\log\mu'_n(x)\to\hb(0.1)\approx0.469$ and $-\frac1n\log\mu''_n(x)=1$; the larger3932probability dominates the sum and the limit is $\hb(0.1)$. On the second component the number of ones is3933$\tfrac12n+o(n)$, so $-\frac1n\log\mu'_n(x)\to\tfrac12\log10+\tfrac12\log\tfrac{10}{9}\approx1.737$, and the limit is $1$.3934 3935\sol{6.5} The two sequences are exchanged by $T$, so the only invariant sets are null or conull, while3936each of them is fixed by $T^2$ and is a $T^2$-invariant set of measure $\tfrac12$. Every block has one of3937two values, so $H_n\le1$ and $H(\mu)=0$.3938%% ---- end sol/06.tex ----3939%% ---- begin sol/07.tex ----3940\section*{Chapter 7}