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

4061$H(p)\approx1.846$.4062 4063\sol{11.2} In the proof of \cref{thm:noiseless}, $L-H(p)=\KL pq-\log K$ with both terms nonnegative. Equality4064needs $K=1$ and $p=q$, so $p(x)=2^{-\ell(x)}$. Conversely if every $p(x)$ is a power of $\tfrac12$ the lengths4065$-\log p(x)$ satisfy Kraft's inequality with equality.4066 4067\sol{11.3} Let the channel code have $M$ messages, of which message $1$ is always decoded wrongly and the4068others always correctly; its average error is $1/M$. Let the compression send a set of source blocks of4069probability $0.9$ to message $1$. The composite fails with probability at least $0.9$. Repair: discard the4070worse half of the messages. If the average error is $\varepsilon$, at most half of the messages have error above4071$2\varepsilon$, so the remaining $M/2$ form a code with maximal error $2\varepsilon$, at a cost of one bit.4072 4073\sol{11.4} If $f$ factors through $[r]$ so does every composite with $f$, which gives (i); if $f,g$ factor4074through $[r],[s]$ then $f\otimes g$ factors through $[rs]$, which gives (ii). For (iii), if $f\colon[M]\to[M]$ has4075diagonal at least $1-\varepsilon$ and factors through $[r]$, then4076$(1-\varepsilon)\log M-1\le C(f)\le\log r$ by Fano's inequality and \cref{prop:capacity}(iv). The bound is4077$\frac1n\log M^*(W^{\otimes n},\varepsilon)\le(\log r_+(W)+\frac1n)/(1-\varepsilon)$. For a binary symmetric channel with4078$0<\delta<\tfrac12$, $r_+=2$ and $\Phi=1>1-\hb(\delta)$. The function $\log\min\{|X|,|Y|\}$ fails (i): a composite4079$X\to1\to X$ has $\Phi=\log|X|$ while each factor has $\Phi=0$.4080 4081\sol{11.5} $W^-$: the decoder sees $y_1,y_2$ and wants $u_1=x_1\oplus x_2$, which is known iff neither output is4082erased; the erasure probability is $1-(1-e)^2$. $W^+$: given $u_1$, the bit $u_2$ equals $x_2$ and equals4083$x_1\oplus u_1$, so it is unknown iff both outputs are erased, with probability $e^2$. Next,4084$f(2e-e^2)=f(e)\sqrt{(2-e)(1-e)}$ and $f(e^2)=f(e)\sqrt{e(1+e)}$, and by the Cauchy--Schwarz inequality4085$\sqrt{(2-e)(1-e)}+\sqrt{e(1+e)}\le\sqrt{(2-e)+(1+e)}\,\sqrt{(1-e)+e}=\sqrt3$. Hence the average of $f(e_b)$ over4086the $2^n$ channels is at most $(\tfrac{\sqrt3}{2})^n f(e)$, and by Markov's inequality the fraction with4087$e_b\in[\delta,1-\delta]$, where $f\ge\sqrt{\delta(1-\delta)}$, tends to zero geometrically. The mean of $e_b$ is4088conserved, so the fraction with $e_b<\delta$ tends to $1-e$.4089%% ---- end sol/11.tex ----4090%% ---- begin sol/12.tex ----4091\section*{Chapter 12}4092 4093\sol{12.1} In $C_5$ any three vertices contain two adjacent ones, and $\{0,2\}$ is independent. Two words4094$(i,2i)$ and $(j,2j)$ with $i\ne j$ are confusable only if $i-j\in\{0,\pm1\}$ and $2(i-j)\in\{0,\pm1\}$ modulo4095$5$; for $i-j=\pm1$ the second difference is $\pm2$. For the capacity, $H(Y\st X)=1$ for every input and4096the uniform input gives the uniform output, so $C=\log5-1$.4097 4098\sol{12.2} For $0<\alpha<1$ the function $t\mapsto t^\alpha$ is concave, so $\sum_iq_i^\alpha=\sum_i(\sum_jD_{ij}p_j)^\alpha\ge\sum_{i,j}D_{ij}p_j^\alpha=\sum_jp_j^\alpha$,4099and $H_\alpha=\frac1{1-\alpha}\log\sum p^\alpha$ increases. For $\alpha>1$ the inequality reverses and so does the sign of4100$1-\alpha$. The cases $\alpha=0,1,\infty$ follow by continuity, or directly. Then use additivity:4101$H_\alpha(p^{\otimes n})=nH_\alpha(p)$.4102 4103\sol{12.3} (i) Every block in the support has positive probability, so $d\circ e$ must be the identity on all4104$|\supp p|^n$ of them, and conversely that many messages suffice. For the numbers: $\hb(\tau)=0.7$ gives4105$\tau\approx0.1893$, and $\KL{(1-\tau,\tau)}{p}\approx0.0521$. The supremum of $\rho(0.7-H_{1/(1+\rho)}(p))$ is attained near4106$\rho\approx0.51$ and is also $0.0521$. The first expression is the exponent of the probability that a block has4107more than $\tau n$ ones, which is the event that the best set of $2^{nR}$ blocks misses it.4108 4109\sol{12.4} Let $a_n$ be the number of allowed blocks of length $n$. An allowed block ends in $0$, preceded by4110any allowed block of length $n-1$, or in $01$, preceded by any allowed block of length $n-2$; so4111$a_n=a_{n-1}+a_{n-2}$ with $a_1=2$, $a_2=3$, and $a_n$ grows like $\phi^n$ with $\phi=\frac{1+\sqrt5}2$. A Markov chain4112with $q_{01}=a$ and $q_{10}=1$ has stationary distribution $(\frac1{1+a},\frac{a}{1+a})$ and entropy $\hb(a)/(1+a)$. Its4113derivative vanishes when $(1+a)\log\frac{1-a}{a}=\hb(a)$, that is, $(1-a)^2=a$, so $a=\frac{3-\sqrt5}2=\phi^{-2}$, and the4114maximum is $\log\phi$.4115 4116\sol{12.5} The entropies are $1$, $\log3\approx1.585$, $2$ and $2$. By \cref{thm:ornstein} and \cref{thm:KS}, one4117Bernoulli shift is a factor of another iff its entropy is not larger. So $B(\tfrac12,\tfrac12)$ is a factor of4118the other three, $B(\tfrac13,\tfrac13,\tfrac13)$ is a factor of Meshalkin's two, and those two are isomorphic. No4119other factor relations hold.4120%% ---- end sol/12.tex ----4121\backmatter4122%% ---- begin bib.tex ----4123\chapter{References}4124\begingroup\small4125\renewcommand{\chapter}[2]{}4126\begin{thebibliography}{FGLPS26}\setlength{\itemsep}{1pt}4127\newcommand{\bi}[1]{\bibitem[#1]{#1}}4128\bi{AC88} P. Algoet and T. Cover. A sandwich proof of the Shannon--McMillan--Breiman theorem. \emph{Ann. Probab.} 16 (1988).4129\bi{AD75} J. Acz\'el and Z. Dar\'oczy. \emph{On Measures of Information and Their Characterizations}. Academic Press, 1975.4130\bi{Adl61} R. Adler. Ergodic and mixing properties of infinite memory channels. \emph{Proc. Amer. Math. Soc.} 12 (1961).4131\bi{Alo98} N. Alon. The Shannon capacity of a union. \emph{Combinatorica} 18 (1998).4132\bi{Ari09} E. Ar\i kan. Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. \emph{IEEE Trans. Inform. Theory} 55 (2009).4133\bi{AT09} E. Ar\i kan and E. Telatar. On the rate of channel polarization. \emph{Proc. IEEE ISIT} (2009).4134\bi{BB15} P. Baudot and D. Bennequin. The homological nature of entropy. \emph{Entropy} 17 (2015).4135\bi{BF14} J. Baez and T. Fritz. A Bayesian characterization of relative entropy. \emph{Theory Appl. Categ.} 29 (2014).4136\bi{BFL11} J. Baez, T. Fritz and T. Leinster. A characterization of entropy in terms of information loss. \emph{Entropy} 13 (2011).4137\bi{Bil65} P. Billingsley. \emph{Ergodic Theory and Information}. Wiley, 1965.4138\bi{Bir31} G. D. Birkhoff. Proof of the ergodic theorem. \emph{Proc. Nat. Acad. Sci. USA} 17 (1931).4139\bi{Bla57} D. Blackwell. The entropy of functions of finite-state Markov chains. \emph{Trans. First Prague Conf. Information Theory} (1957).4140\bi{BMSS12} L. Birkedal, R. M\o gelberg, J. Schwinghammer and K. St\o vring. First steps in synthetic guarded domain theory: step-indexing in the topos of trees. \emph{Log. Methods Comput. Sci.} 8(4) (2012).4141\bi{Bra21} T.-D. Bradley. Entropy as a topological operad derivation. \emph{Entropy} 23 (2021).4142\bi{Bre57} L. Breiman. The individual ergodic theorem of information theory. \emph{Ann. Math. Statist.} 28 (1957); correction, 31 (1960).4143\bi{Bre60} L. Breiman. On achieving channel capacity in finite-memory channels. \emph{Illinois J. Math.} 4 (1960).4144\bi{Cat88} J.-L. Cathelineau. Sur l'homologie de $\mathrm{SL}_2$ \`a coefficients dans l'action adjointe. \emph{Math. Scand.} 63 (1988).4145\bi{Cen82} N. N. \v{C}encov. \emph{Statistical Decision Rules and Optimal Inference}. Amer. Math. Soc., 1982.4146\bi{CFS16} B. Coecke, T. Fritz and R. Spekkens. A mathematical theory of resources. \emph{Inform. and Comput.} 250 (2016).4147\bi{Chu61} K. L. Chung. A note on the ergodic theorem of information theory. \emph{Ann. Math. Statist.} 32 (1961).4148\bi{CJ19} K. Cho and B. Jacobs. Disintegration and Bayesian inversion via string diagrams. \emph{Math. Structures Comput. Sci.} 29 (2019).4149\bi{CK11} I. Csisz\'ar and J. K\"orner. \emph{Information Theory: Coding Theorems for Discrete Memoryless Systems}, 2nd ed. Cambridge Univ. Press, 2011.4150\bi{CT06} T. Cover and J. Thomas. \emph{Elements of Information Theory}, 2nd ed. Wiley, 2006.4151\bi{Dar70} Z. Dar\'oczy. Generalized information functions. \emph{Inform. and Control} 16 (1970).4152\bi{DDGK16} F. Dahlqvist, V. Danos, I. Garnier and O. Kammar. Bayesian inversion by $\omega$-complete cone duality. \emph{Proc. CONCUR 2016}.4153\bi{DGB13} D. Dikranjan and A. Giordano Bruno. Entropy in a category. \emph{Appl. Categ. Structures} 21 (2013).4154\bi{DHKK14} G. Dimitrov, F. Haiden, L. Katzarkov and M. Kontsevich. Dynamical systems and categories. \emph{Contemp. Math.} 621 (2014).4155\bi{Dob59} R. L. Dobrushin. General formulation of Shannon's main theorem in information theory. \emph{Uspekhi Mat. Nauk} 14 (1959).4156\bi{Doo53} J. L. Doob. \emph{Stochastic Processes}. Wiley, 1953.4157\bi{EP23} N. Ensarguet and P. Perrone. Categorical probability spaces, ergodic decompositions, and transitions to equilibrium. arXiv:2310.04267 (2023).4158\bi{Erd46} P. Erd\H{o}s. On the distribution function of additive functions. \emph{Ann. of Math.} 47 (1946).4159\bi{EVG02} P. Elbaz-Vincent and H. Gangl. On poly(ana)logs I. \emph{Compositio Math.} 130 (2002).4160\bi{Fad56} D. K. Faddeev. On the concept of entropy of a finite probabilistic scheme. \emph{Uspekhi Mat. Nauk} 11 (1956).