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

3861$(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}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$.