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 3649–3748 of 4249. Source text is displayed literally.
3649\renewcommand{\arraystretch}{1.22}3650\begin{longtable}{@{}p{0.47\textwidth}p{0.45\textwidth}@{}}3651\toprule3652\textbf{Khinchin} & \textbf{This book}\\\midrule3653\endhead3654\multicolumn{2}{@{}l}{\emph{The Entropy Concept in Probability Theory} (1953)}\\3655\S1 Entropy of finite schemes & \cref{ch:schemes}\\3656\S2 The uniqueness theorem & \cref{ch:uniqueness,ch:cocycle}\\3657\S3 Entropy of Markov chains & \cref{ch:sources}, \cref{prop:markov}\\3658\S4 Fundamental theorems (Theorems 2, 3) & \cref{ch:aep}, \cref{thm:mcmillan,thm:counting}\\3659\S5 Application to coding theory (Theorem 4) & \cref{ch:shannon}, \cref{thm:noiseless}\\[4pt]3660\multicolumn{2}{@{}l}{\emph{On the Fundamental Theorems of Information Theory} (1956)}\\3661Ch.~I, \S1 Two generalizations of Shannon's inequality & \cref{ch:inequalities}, \cref{lem:partial,lem:SSA}\\3662Ch.~I, \S2 Three inequalities of Feinstein & \cref{lem:feinstein3}\\3663Ch.~II, \S3 Source, stationarity, entropy & \cref{ch:sources}, \cref{prop:rate}\\3664Ch.~II, \S4 Ergodic sources & \cref{ch:ergodic}\\3665Ch.~II, \S5 The $E$ property; McMillan's theorem & \cref{ch:aep}\\3666Ch.~II, \S6 Martingales; Doob's theorem & \cref{ch:martingales}\\3667Ch.~II, \S7 Auxiliary propositions & \cref{lem:tail,lem:gk}\\3668Ch.~II, \S8 Proof of McMillan's theorem & \cref{thm:mcmillan}\\3669Ch.~III, \S9 Channel, noise, stationarity, anticipation, memory & \cref{def:channel,prop:natural}\\3670Ch.~III, \S10 Connection of the channel to the source & \cref{thm:stationary}\\3671Ch.~III, \S11 The ergodic case & \cref{ex:gap,thm:ergodicchannel}\\3672Ch.~IV, \S\S12--13 Feinstein's fundamental lemma & \cref{ch:feinstein}, \cref{thm:feinstein,thm:feinsteinmem}\\3673Ch.~V, \S14 Coding & \cref{ch:shannon}\\3674Ch.~V, \S15 The first Shannon theorem & \cref{thm:shannon1}\\3675Ch.~V, \S16 The second Shannon theorem & \cref{thm:shannon2}\\3676Conclusion & \cref{thm:capacities}, \cref{ch:coda}\\3677\bottomrule3678\end{longtable}3679\end{center}3680 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}.\\