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

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).4161\bi{Fan61} R. Fano. \emph{Transmission of Information}. MIT Press, 1961.4162\bi{Fei54} A. Feinstein. A new basic theorem of information theory. \emph{IRE Trans. Inform. Theory} 4 (1954).4163\bi{Fei58} A. Feinstein. \emph{Foundations of Information Theory}. McGraw-Hill, 1958.4164\bi{Fei59} A. Feinstein. On the coding theorem and its converse for finite-memory channels. \emph{Inform. and Control} 2 (1959).4165\bi{FGLPS26} T. Fritz, T. Gonda, A. Lorenzin, P. Perrone and A. Shah Mohammed. Empirical measures and strong laws of large numbers in categorical probability. \emph{Log. Methods Comput. Sci.} 22(2) (2026).4166\bi{FR20} T. Fritz and E. F. Rischel. Infinite products and zero-one laws in categorical probability. \emph{Compositionality} 2 (2020).4167\bi{Fri17} T. Fritz. Resource convertibility and ordered commutative monoids. \emph{Math. Structures Comput. Sci.} 27 (2017).4168\bi{Fri20} T. Fritz. A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics. \emph{Adv. Math.} 370 (2020).4169\bi{Fuj78} S. Fujishige. Polymatroidal dependence structure of a set of random variables. \emph{Inform. and Control} 39 (1978).4170\bi{FuP21} J. Fullwood and A. Parzygnat. The information loss of a stochastic map. \emph{Entropy} 23 (2021).4171\bi{Gir82} M. Giry. A categorical approach to probability theory. \emph{Lecture Notes in Math.} 915 (1982).4172\bi{Gla03} E. Glasner. \emph{Ergodic Theory via Joinings}. Amer. Math. Soc., 2003.4173\bi{Gra09} R. Gray. \emph{Probability, Random Processes, and Ergodic Properties}, 2nd ed. Springer, 2009.4174\bi{Gra11} R. Gray. \emph{Entropy and Information Theory}, 2nd ed. Springer, 2011.4175\bi{Gro13} M. Gromov. In a search for a structure, Part 1: On entropy. Preprint, 2013.4176\bi{Hae79} W. Haemers. On some problems of Lov\'asz concerning the Shannon capacity of a graph. \emph{IEEE Trans. Inform. Theory} 25 (1979).4177\bi{Han03} T. S. Han. \emph{Information-Spectrum Methods in Information Theory}. Springer, 2003.4178\bi{HC67} J. Havrda and F. Charv\'at. Quantification method of classification processes: concept of structural $a$-entropy. \emph{Kybernetika} 3 (1967).4179\bi{Hed69} G. Hedlund. Endomorphisms and automorphisms of the shift dynamical system. \emph{Math. Systems Theory} 3 (1969).4180\bi{HJS07} I. Hasuo, B. Jacobs and A. Sokolova. Generic trace semantics via coinduction. \emph{Log. Methods Comput. Sci.} 3(4) (2007).4181\bi{Hu62} Hu Kuo Ting. On the amount of information. \emph{Theory Probab. Appl.} 7 (1962).4182\bi{Huf52} D. Huffman. A method for the construction of minimum-redundancy codes. \emph{Proc. IRE} 40 (1952).4183\bi{HV93} T. S. Han and S. Verd\'u. Approximation theory of output statistics. \emph{IEEE Trans. Inform. Theory} 39 (1993).4184\bi{Jac59} K. Jacobs. Die \"Ubertragung diskreter Informationen durch periodische und fastperiodische Kan\"ale. \emph{Math. Ann.} 137 (1959).4185\bi{JV20} A. Jensen and P. Vrana. The asymptotic spectrum of LOCC transformations. \emph{IEEE Trans. Inform. Theory} 66 (2020).4186\bi{Ken64} D. G. Kendall. Functional equations in information theory. \emph{Z. Wahrscheinlichkeitstheorie verw. Gebiete} 2 (1964).4187\bi{Khi53} A. I. Khinchin. The entropy concept in probability theory. \emph{Uspekhi Mat. Nauk} 8(3) (1953). English translation in \cite{Khi57}.4188\bi{Khi56} A. I. Khinchin. On the fundamental theorems of information theory. \emph{Uspekhi Mat. Nauk} 11(1) (1956). English translation in \cite{Khi57}.