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

3729\ref{ch:ergodic} & \Cref{ex:mixture}, including the bound of one bit on the excess; the criterion of3730 \cref{exer:cylinders} for a Markov chain and its failure for the mixture; affinity of the entropy on a3731 segment of stationary Markov sources.\\3732\ref{ch:martingales} & Idempotence, symmetry and the tower property for conditional expectations on finite3733 spaces, and a pair that does not commute; the dyadic martingale; the likelihood-ratio martingale of3734 \cref{exer:likelihood}, including the singularity of the limit; the mean ergodic theorem for a permutation;3735 orthogonality of martingale increments.\\3736\ref{ch:aep} & \Cref{lem:tail} for the Markov and hidden Markov sources; \cref{ex:counting,ex:mixcount}; the3737 second-order prediction of \cref{exer:second}.\\3738\ref{ch:channels} & Invariance of the compound source in a cyclic model (\cref{thm:stationary}); \cref{ex:gap};3739 the capacities of \cref{ex:channels} by the Blahut--Arimoto iteration against the closed forms; the four3740 statements of \cref{prop:capacity} and the sum formula; symmetry of the rate under the dagger; naturality of3741 a memoryless family (\cref{prop:natural}); \cref{ex:isi}.\\3742\ref{ch:feinstein} & The greedy construction of \cref{thm:feinstein} on 40 random channels: whenever the3743 guaranteed error is below $1$ it produces at least $M$ codewords with disjoint decoding sets and that3744 maximal error. The estimate \eqref{eq:QE}; the weak converse for the codes found; \cref{ex:feinsteinbsc};3745 exact $\varepsilon$-ranks of small channels by exhaustive search.\\3746\ref{ch:shannon} & Kraft's inequality and the bounds of \cref{thm:noiseless} for Huffman codes;3747 \cref{ex:huffman}; \cref{lem:compose} on an explicit composite; \cref{prop:polar}, including the bound from3748 Mrs.~Gerber's lemma, on five channels; \cref{ex:polar} and the orthogonality argument of \cref{thm:polar}.\\3749\ref{ch:rates} & \Cref{ex:pentagon} by exhaustive search for independent sets, and Lov\'asz's orthonormal3750 representation; monotonicity of all R\'enyi entropies under doubly stochastic maps; agreement of the two3751 expressions for the exponent in \cref{thm:exponent}; \cref{prop:collapse} for independent bits at $n=2000$;3752 \cref{ex:golden}; the entropies in \cref{thm:ornstein}.\\3753\ref{app:solutions} & The numerical answers to Exercises 1.1, 1.4, 1.5, 2.1, 2.4, 3.2, 3.5, 4.1, 4.3--4.5,3754 5.1, 5.3, 6.1, 6.4, 7.1, 7.5, 8.1, 8.5, 9.1, 10.2, 10.3, 10.5, 11.1, 11.4, 11.5, 12.2, 12.3 and 12.5.\\3755\bottomrule3756\end{longtable}3757\end{center}3758 3759\noindent The checks on random instances use a few dozen to a few hundred instances each. They would detect3760a wrong sign or a misplaced hypothesis; they say nothing about measure-theoretic statements, which are3761outside the reach of a finite computation.3762%% ---- end ch/C-computations.tex ----3763%% ---- begin ch/D-solutions.tex ----3764\chapter{Solutions to the Exercises}\label{app:solutions}3765 3766Solutions are given for every exercise, numbered as in the chapters. Where an exercise asks for a3767computation, the numbers below are recomputed by the script of \cref{app:computations}.3768%% ---- end ch/D-solutions.tex ----3769%% ---- begin sol/01.tex ----3770\section*{Chapter 1}3771 3772\sol{1.1} $g$ has image $(\tfrac34,\tfrac18,\tfrac18)$ and one nontrivial fibre, of mass $\tfrac34$ and conditional3773distribution $(\tfrac23,\tfrac13)$: $H(g)=\tfrac34\hb(\tfrac23)\approx0.689$. Then $h$ has image3774$(\tfrac34,\tfrac14)$ and one nontrivial fibre of mass $\tfrac14$ and conditional distribution3775$(\tfrac12,\tfrac12)$: $H(h)=0.25$. The composite has $H(h\circ g)=H(p)-\hb(\tfrac14)\approx1.75-0.811=0.939$, the3776sum of the two.3777 3778\sol{1.2} $H(f)=H(p)-H(f_*p)$ and $H(f_*p)=0$ iff $f_*p$ is a point mass. If $f$ is an isomorphism then3779$H(f)=0$ since $f$ is injective, so $H(p)=H(q)$. The converse fails: $(\tfrac12,\tfrac14,\tfrac18,\tfrac18)$3780and $(a,a,b,b,b,b)$ with $2a+4b=1$ can be given the same entropy $1.75$ by the intermediate value theorem3781($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 ----