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 3901–4000 of 4249. Source text is displayed literally.
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$.3961 3962\sol{7.5} $\sigma$ has order $6$, so $\frac16\sum_{k<6}U^k$ averages a function over the orbits of $\sigma$: it is block3963diagonal with blocks $\tfrac13J_3$ and $\tfrac12J_2$. This is the conditional expectation, for the uniform3964distribution, onto the $\sigma$-algebra generated by the cycles, which is the invariant $\sigma$-algebra.3965%% ---- end sol/07.tex ----3966%% ---- begin sol/08.tex ----3967\section*{Chapter 8}3968 3969\sol{8.1} $i_n=\sum_{k<n}-\log p(x_k)$ is a sum of independent identically distributed terms with mean $H$ and3970variance $\sigma^2$, so $\frac1ni_n$ has variance $\sigma^2/n$. For a bit with $\Prob(1)=p$ the term takes two values3971differing by $\log\frac{1-p}{p}$, so $\sigma^2=p(1-p)\log^2\frac{1-p}{p}$; at $p=0.2$ this is $0.16\cdot4=0.64$.3972 3973\sol{8.2} By the Markov property $\mu(x_0\st x_{-k},\dots,x_{-1})=q_{x_{-1}x_0}$ for $k\ge1$. So3974$i_n=g_0+\sum_{k=1}^{n-1}g_1\circ T^k$ with $g_1$ bounded on the support of $\mu$, and3975$\frac1ni_n\to\E[g_1\st\II]$ in $L^1$, which is $\E g_1=H(\mu)$ if the source is ergodic.3976 3977\sol{8.3} Each block of $T_n^\varepsilon$ has probability at least $2^{-n(H+\varepsilon)}$ and the total is at most $1$;3978each has probability at most $2^{-n(H-\varepsilon)}$ and the total is at least $1-\delta$. For \cref{prop:uniform}3979take $S=T_n^\varepsilon$ with $n$ so large that $\mu_n(S)\ge1-\varepsilon\ge\tfrac12$. Then3980$\tfrac12\,2^{n(H-\varepsilon)}\le|S|\le2^{n(H+\varepsilon)}$, and $\mu_n(C)|S|$ lies between3981$\tfrac12\,2^{-2n\varepsilon}$ and $2^{2n\varepsilon}$.3982 3983\sol{8.4} Order the blocks by decreasing probability, which is by increasing number of ones. By3984Exercise~6.4 the blocks with about $0.1n$ ones carry probability close to $\tfrac12$ in total and each has3985probability about $\tfrac12\,2^{-n\hb(0.1)}$; there are about $2^{n\hb(0.1)}$ of them. If $\lambda<\tfrac12$ they3986suffice. If $\lambda>\tfrac12$ one must add blocks from the second component, which have probability about3987$\tfrac12\,2^{-n}$ each, and a fixed positive fraction of all $2^n$ blocks is needed.3988 3989\sol{8.5} The probability of a block decreases with its number of ones, so an optimal set consists of all3990blocks with fewer than $k$ ones and some with exactly $k$, where $k=np+\Phi^{-1}(\lambda)\sqrt{np(1-p)}+o(\sqrt n)$ by3991the central limit theorem. The number of such blocks is $2^{n\hb(k/n)+O(\log n)}$, and3992$\hb(k/n)=\hb(p)+\hb'(p)(k/n-p)+O(1/n)$ with $\hb'(p)=\log\frac{1-p}{p}$. For $p=0.2$, $\sigma=0.8$; at $n=1000$ the3993correction for $\lambda=0.9$ is $0.8\cdot1.2816/\sqrt{1000}\approx0.032$, predicting $0.754$ against the computed3994$0.748$, and for $\lambda=0.1$ predicting $0.690$ against $0.683$. The remaining difference is the term of order3995$(\log n)/n$.3996%% ---- end sol/08.tex ----3997%% ---- begin sol/09.tex ----3998\section*{Chapter 9}3999 4000\sol{9.1} Erasure: the output reveals whether an erasure occurred, so $H(Y)=\hb(e)+(1-e)H(p)$ and