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

3681\noindent Topics treated here that have no counterpart in the source: the functorial and operadic3682characterizations of entropy (\cref{ch:uniqueness}); information cohomology and entropy modulo a prime3683(\cref{ch:cocycle}); relative entropy and the enriched structure (\cref{ch:inequalities}); coalgebraic sources3684(\cref{ch:sources}); the categorical ergodic decomposition (\cref{ch:ergodic}); the converse coding theorem and3685polar codes (\cref{ch:shannon}); zero-error capacity, asymptotic spectra and the isomorphism theory of3686Bernoulli shifts (\cref{ch:rates}).3687%% ---- end ch/B-concordance.tex ----3688%% ---- begin ch/C-computations.tex ----3689\chapter{Computational Checks}\label{app:computations}3690 3691The script \texttt{verify.py} that accompanies this book recomputes every numerical example in the text3692and in the solutions, and tests a number of structural claims on explicit or randomly generated finite3693instances. It uses only the Python standard library, fixes its random seed, and runs in about a second;3694\texttt{python3 verify.py} prints one line per check and exits with status zero if and only if all pass.3695Version~1.0 performs 91 checks, all of which pass under Python~3.8 or later.3696 3697A check of this kind is evidence about the examples and about the absence of slips in the finite3698statements. It is not a proof of any theorem, and the theorems tagged \textsf{classical} or3699\textsf{literature} rest on the references cited for them. What the script does establish is the3700following.3701 3702\begin{center}\small3703\renewcommand{\arraystretch}{1.25}3704\begin{longtable}{@{}p{0.09\textwidth}p{0.83\textwidth}@{}}3705\toprule3706\textbf{Ch.} & \textbf{What is checked}\\\midrule3707\endhead3708\ref{ch:schemes} & \Cref{ex:first,ex:coarse}. On random instances: $H(f)=H(p)-H(q)$ and functoriality3709 (\cref{thm:functor}); the operadic chain rule; convex-linearity (\cref{prop:convexlinear}); Khinchin's3710 properties; \cref{prop:lossnoise}.\\3711\ref{ch:uniqueness} & The second step of Khinchin's proof on random rational distributions. Additivity,3712 maximality and expansibility of the R\'enyi entropies, their limit at $\alpha=1$, and \cref{ex:renyi}. The3713 Leibniz rule \eqref{eq:leibniz} for $H$ and its failure for $H_2$.\\3714\ref{ch:cocycle} & On random observables and laws on a five-point space: the action axiom for3715 $\alpha=1,\tfrac12,2$ (\cref{lem:action}); the cocycle condition for entropy (\cref{prop:Hcocycle});3716 $\delta\delta=0$ on a generic local cochain; the Tsallis coboundary and cocycle identities and the limit3717 $\alpha\to1$ (\cref{thm:tsallis,prop:obstruction}). The fundamental equation for $\hb$ and for $h(x)=x$, and,3718 in a four-dimensional test space, that its solutions are spanned by $\hb$. The Leibniz rule for the Fermat3719 quotient; that entropy modulo $p$ is well defined, satisfies the chain rule, equals the truncated3720 logarithm and satisfies the fundamental equation, for $p=3,5,7,11,13$ (\cref{thm:modp}).\\3721\ref{ch:inequalities} & On random instances: Gibbs' inequality, the chain rule and data processing; the3722 three statements of \cref{thm:enriched}; \cref{prop:copy}; \cref{lem:partial}; monotonicity and submodularity3723 on the lattice of partitions, with the meet computed explicitly (\cref{prop:submodular}); the three3724 inequalities of \cref{lem:feinstein3}; functoriality of relative entropy on $\FinStat$.\\3725\ref{ch:sources} & \Cref{ex:markov,ex:hmm}, by exact enumeration of block laws; monotonicity of the two3726 bounds of \cref{thm:blackwell}; stationarity of a coalgebraic source; that a sliding block code does not3727 raise block entropies; the count of equivariant maps in \cref{exer:cofreefinite}; \cref{prop:unifilar} on an3728 example.\\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 theorem