%% Entropy, Sources, and Channels in Higher Categories
%% Cocycles, Markov categories, and coding in the mathematical foundations of information theory
%% Single-file LaTeX source (UTF-8), version 1.0, 2026-11-16.
%% Includes Appendix D, solutions to all 60 exercises.
%% Build: pdflatex (three passes). Requires only standard TeX Live packages
%% (mathpazo, amsmath, amsthm, mathtools, stmaryrd, tikz, tikz-cd, booktabs, longtable,
%%  enumitem, titlesec, fancyhdr, caption, hyperref, cleveref, microtype).
%% Companion script: verify.py (91 computational checks).
\documentclass[11pt,openany]{book}
%% ---- begin preamble.tex ----
% ---------- fonts and page ----------
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[sc,osf]{mathpazo}
\linespread{1.05}
\usepackage[scaled=0.9]{helvet}
\usepackage[paperwidth=7in,paperheight=10in,inner=0.95in,outer=0.85in,top=0.95in,bottom=1.0in,headsep=14pt]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools,stmaryrd}
\usepackage{microtype}
\usepackage{xcolor}
\definecolor{accent}{HTML}{7A1F2B}
\definecolor{ink2}{HTML}{4A5560}
\definecolor{fwd}{HTML}{1F4E79}
\definecolor{bwd}{HTML}{A8432C}
\usepackage{tikz,tikz-cd}
\usetikzlibrary{arrows.meta,positioning,calc,decorations.markings,shapes.geometric,backgrounds,fit}
\usepackage{booktabs,array,tabularx,longtable}
\usepackage{enumitem}
\setlist{itemsep=2pt,topsep=4pt}
\usepackage{titlesec}
\usepackage{fancyhdr}
\usepackage[font=small,labelfont={bf,sf},margin=1.5em]{caption}
\usepackage[colorlinks=true,linkcolor=accent,citecolor=accent,urlcolor=accent,
  pdftitle={Entropy, Sources, and Channels in Higher Categories},
  pdfsubject={The mathematical foundations of information theory in higher categorical semantics},
  pdfkeywords={entropy, information cohomology, Markov categories, ergodic sources, Shannon-McMillan theorem, channel capacity, Feinstein lemma, operads}]{hyperref}
\usepackage[nameinlink,capitalise,noabbrev]{cleveref}

% ---------- headings ----------
\titleformat{\chapter}[display]{\normalfont\Large\scshape\color{accent}}{\chaptertitlename\ \thechapter}{4pt}{\normalfont\huge\bfseries\color{black}}
\titlespacing*{\chapter}{0pt}{10pt}{26pt}
\titleformat{\section}{\normalfont\large\bfseries}{\thesection}{0.7em}{}
\titleformat{\subsection}{\normalfont\normalsize\bfseries\itshape}{\thesubsection}{0.7em}{}
\titleformat{\part}[display]{\normalfont\centering\Large\scshape\color{accent}}{\partname\ \thepart}{12pt}{\normalfont\Huge\bfseries\color{black}}
\pagestyle{fancy}\fancyhf{}
\fancyhead[LE]{\small\thepage\quad\textsc{\nouppercase{\leftmark}}}
\fancyhead[RO]{\small\textsc{\nouppercase{\rightmark}}\quad\thepage}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\chaptermark}[1]{\markboth{#1}{#1}}
\renewcommand{\sectionmark}[1]{\markright{\thesection\ \ #1}}
\fancypagestyle{plain}{\fancyhf{}\fancyfoot[C]{\small\thepage}}
\setlength{\headheight}{14pt}
\setcounter{tocdepth}{1}
\setcounter{secnumdepth}{2}
\raggedbottom
\emergencystretch=2em
\tolerance=1200
\hbadness=2000

% ---------- theorem environments ----------
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[chapter]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{principle}[theorem]{Principle}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{construction}[theorem]{Construction}
\newtheorem{problem}[theorem]{Open Problem}
\newtheorem{exercise}{Exercise}[chapter]
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\crefname{principle}{Principle}{Principles}
\crefname{construction}{Construction}{Constructions}
\crefname{conjecture}{Conjecture}{Conjectures}
\crefname{exercise}{Exercise}{Exercises}
\crefname{problem}{Open Problem}{Open Problems}

% ---------- status tags ----------
\newcommand{\stag}[2]{{\footnotesize\sffamily\upshape\color{#1}[#2]}\enspace\ignorespaces}
\newcommand{\Scl}[1][]{\stag{ink2}{classical\if\relax\detokenize{#1}\relax\else; #1\fi}}
\newcommand{\Sli}[1][]{\stag{fwd}{literature\if\relax\detokenize{#1}\relax\else; #1\fi}}
\newcommand{\Srf}[1][]{\stag{accent}{reformulation\if\relax\detokenize{#1}\relax\else; cf.\ #1\fi}}
\newcommand{\Sob}{\stag{accent}{observation}}
\newcommand{\Spg}{\stag{bwd}{programme}}

% ---------- notation ----------
\newcommand{\cat}[1]{\mathsf{#1}}
\newcommand{\Set}{\cat{Set}}
\newcommand{\FinSet}{\cat{FinSet}}
\newcommand{\Meas}{\cat{Meas}}
\newcommand{\Stoch}{\cat{Stoch}}
\newcommand{\FinStoch}{\cat{FinStoch}}
\newcommand{\BorelStoch}{\cat{BorelStoch}}
\newcommand{\FinProb}{\cat{FinProb}}
\newcommand{\FinStat}{\cat{FinStat}}
\newcommand{\Krn}{\cat{Krn}}
\newcommand{\Hilb}{\cat{Hilb}}
\newcommand{\Ban}{\cat{Ban}}
\newcommand{\Src}{\cat{Src}}
\newcommand{\Chan}{\cat{Chan}}
\newcommand{\Dyn}{\cat{Dyn}}
\newcommand{\Cat}{\cat{Cat}}
\newcommand{\CC}{\mathcal{C}}
\newcommand{\FF}{\mathcal{F}}
\newcommand{\GG}{\mathcal{G}}
\newcommand{\II}{\mathcal{I}}
\newcommand{\Sinf}{\mathcal{S}}
\newcommand{\Qlaw}{\mathcal{Q}}
\newcommand{\Fun}{\mathcal{F}}
\newcommand{\Dist}{\Delta}
\newcommand{\Giry}{\mathcal{G}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Rbar}{\overline{\mathbb{R}}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Fp}{\mathbb{F}_p}
\newcommand{\E}{\mathbb{E}}
\newcommand{\Prob}{\mathbb{P}}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\colim}{colim}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\Ext}{Ext}
\DeclareMathOperator{\Fix}{Fix}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\TV}{TV}
\DeclareMathOperator{\rk}{rk}
\newcommand{\id}{\mathrm{id}}
\newcommand{\op}{\mathrm{op}}
\newcommand{\adj}{\dashv}
\newcommand{\iso}{\cong}
\newcommand{\st}{\mid}
\newcommand{\cpy}{\mathrm{copy}}
\newcommand{\del}{\mathrm{del}}
\newcommand{\KL}[2]{D(#1\,\|\,#2)}
\newcommand{\hb}{h}
\newcommand{\AZ}{A^{\Z}}
\newcommand{\BZ}{B^{\Z}}
\newcommand{\term}[1]{\textbf{\itshape #1}}

% ---------- tikz styles ----------
\tikzset{
  ogbox/.style={draw, thick, rounded corners=2pt, minimum width=1.25cm, minimum height=1.05cm, fill=black!4},
  fw/.style={-{Stealth[length=5pt]}, thick, fwd},
  bw/.style={-{Stealth[length=5pt]}, thick, bwd, densely dashed},
  dec/.style={circle, fill, inner sep=1.7pt},
  nat/.style={circle, draw, thick, fill=white, inner sep=1.7pt},
  leaf/.style={inner sep=2pt, font=\small},
  lab/.style={font=\small, inner sep=1.5pt},
  infoset/.style={densely dashed, thick, accent},
  st/.style={circle, draw, thick, fill=white, inner sep=1.6pt},
  ty/.style={rectangle, draw, thick, fill=black!8, inner sep=2.6pt},
}
\newcommand{\sol}[1]{\par\medskip\noindent\textbf{#1.}\enspace\ignorespaces}
\newcommand{\bookauthor}{Anonymous}
%% ---- end preamble.tex ----
\begin{document}
\frontmatter
%% ---- begin front.tex ----
\begin{titlepage}
\thispagestyle{empty}
\vspace*{1.1in}
\noindent{\Large\scshape\color{accent} Higher Categorical Semantics}\par
\vspace{0.9in}
\noindent{\fontsize{30}{38}\selectfont\bfseries\raggedright Entropy, Sources,\\ and Channels\\ in Higher Categories\par}
\vspace{0.35in}
\noindent{\Large\itshape Cocycles, Markov categories, and coding\\[2pt] in the mathematical foundations of information theory}\par
\vfill
\noindent\begin{tikzpicture}[x=1cm,y=1cm]
  \node[ogbox] (mu) at (0,0) {$\mu$};
  \node[dec] (c) at (1.6,0) {};
  \node[ogbox] (nu) at (3.4,-0.65) {$\nu$};
  \draw[fw] (mu) -- (c);
  \draw[fw] (c) |- (5.4,0.65) node[right,lab,black]{$\AZ$};
  \draw[fw] (c) |- (nu);
  \draw[fw] (nu) -- (5.4,-0.65) node[right,lab,black]{$\BZ$};
\end{tikzpicture}\par
\vspace{0.5in}
\noindent{\large \bookauthor}\par
\vspace{4pt}
\noindent{\small 2026}
\end{titlepage}

\thispagestyle{empty}
\vspace*{\fill}
{\small
\noindent\textbf{About this text.}
This monograph is a higher-categorical treatment of the territory mapped by A.~I.~Khinchin's
\emph{Mathematical Foundations of Information Theory} (Dover, 1957; the English translation, by R.~A.~Silverman and
M.~D.~Friedman, of two papers of 1953 and 1956): the entropy of finite schemes and its uniqueness, stationary
and ergodic sources, McMillan's theorem, channels with memory, Feinstein's lemma, and Shannon's coding
theorems. It is an independent work. It reproduces none of that book's text or proofs verbatim; it is not
affiliated with or endorsed by its publisher. \Cref{app:concordance} gives a concordance so that the two can
be read side by side.

\medskip
\noindent\textbf{Status of results.}
Every numbered statement carries a tag: \textsf{classical} (standard information theory, probability or
ergodic theory, attributed), \textsf{literature} (established in the categorical or homological literature,
attributed), \textsf{reformulation} (a known result restated in a different language, with the restatement
proved or sketched here), \textsf{observation} (an elementary remark we have not found stated in this form),
or \textsf{programme} (a conjecture or a direction, not a result). No cited theorem is claimed as new.

\medskip
\noindent\textbf{Authorship and assistance.}
The text was drafted and typeset with a large language model (Anthropic's Claude) under the direction of
the submitting author, who is responsible for it. Generative AI assisted with drafting, literature recall,
mathematical consistency checks, computation, and typesetting. The numerical examples and a number of finite
structural claims are recomputed by the accompanying script \texttt{verify.py} (\cref{app:computations}).
Proofs and bibliographic details have not been independently refereed; corrections are welcome.

\medskip
\noindent Open access. Rights remain with the author.
}
\clearpage

\tableofcontents

\chapter{Preface}

Khinchin's two papers of 1953 and 1956 did for Shannon's theory what Kolmogorov's \emph{Grundbegriffe} had
done for probability: they said what the objects are. A source is a stationary measure on a space of
sequences. A channel is a family of measures on output sequences indexed by input sequences. Entropy is
the function on finite schemes singled out by three properties. The coding theorem is a statement about
these and about nothing else, and it has a proof. The papers are short, they contain almost no examples,
and seventy years on they are still a good place to learn what the theorems say.

They were written in the mathematical language available at the time, which was that of measures on
product spaces. This book rewrites them in a language that was not available. The claim is not that
category theory proves Shannon's theorems; for the most part it does not, and the places where it does not
are marked. The claim is that three features of Khinchin's text, each of which he states in words and then
handles by computation, are structure that can now be named.

The first is the additivity axiom $H(AB)=H(A)+H_A(B)$. It is the condition for a function on observables to be
a 1-cocycle for the action of observables on functions by conditioning, and the uniqueness theorem computes a
cohomology group: $H^1\iso\R$, generated by entropy (\cref{ch:cocycle}). Symmetry of entropy is then
not an axiom but the commutativity of a monoid; the Tsallis entropies are the coboundaries of a deformed
action; and Shannon entropy is what survives when the deformation is switched off.

The second is Khinchin's remark that ``formally every code can be regarded as a channel'', together with
his construction of the compound source. Sources, codes and channels are the states and the morphisms of one
category, that of shift-equivariant Markov kernels. The compound source is a composite, and his theorem
that it is stationary is the statement that composition preserves equivariance (\cref{ch:channels}). The
same category, taken up to almost sure equality, carries a dagger. Conditional expectations are its
idempotents, and the two limits in McMillan's theorem, over longer pasts and over longer times, are limits
of idempotents (\cref{ch:martingales,ch:aep}).

The third is the form of the two asymptotic theorems on which everything rests. McMillan's theorem says that
a long block from an ergodic source is, up to $\varepsilon$, a uniform choice among $2^{nH}$ sequences.
Feinstein's lemma says that a long block of channel uses is, up to $\varepsilon$, an identity map on
$2^{nC}$ messages. Both are statements about approximate retractions, entropy and capacity are the
corresponding ranks, and Shannon's theorem is that retractions compose (\cref{ch:feinstein,ch:shannon}).
What the tolerance $\varepsilon$ buys can be said exactly: without it a whole spectrum of invariants is
needed, and with it the spectrum collapses to a point (\cref{ch:rates}).

The reader will find that the amount of genuinely higher structure varies. The first part uses
homological algebra and operads in earnest. The second and third use monoidal, enriched and dagger
categories, which are low-dimensional. \Cref{ch:coda} says where we think the language earned its place and
where it only relabelled.

\chapter{Introduction}

\section*{What is assumed}

We assume basic category theory (functors, natural transformations, limits, adjunctions, monoidal
categories) and measure-theoretic probability at the level of a first graduate course. Markov categories,
operads, monoid cohomology, enrichment and dagger categories are introduced as needed and collected in
\cref{app:toolkit}. No information theory is assumed; every classical notion is defined, and every classical
theorem is either proved or cited.

Logarithms are to base $2$ unless written $\ln$, so entropies are in bits. We write $\hb(x)=-x\log x-(1-x)\log(1-x)$
for the binary entropy function and use the convention $0\log 0=0$.

\section*{How the book is organized}

\Cref{fig:intro} shows the one picture to keep in mind. A source is a state $\mu$, a channel is a morphism
$\nu$, codes are deterministic morphisms, and using a channel means composing with it. Everything in
Parts~II and III is about this diagram and its finite truncations.

\begin{figure}[ht]\centering
\begin{tikzpicture}[x=1cm,y=1cm]
  \node[ogbox] (mu) at (0,0) {$\mu$};
  \node[ogbox] (e) at (2.3,0) {$e$};
  \node[ogbox] (nu) at (4.6,0) {$\nu$};
  \node[ogbox] (d) at (6.9,0) {$d$};
  \draw[fw] (mu) -- node[above=2pt,lab,black]{$A_0^{\Z}$} (e);
  \draw[fw] (e) -- node[above=2pt,lab,black]{$\AZ$} (nu);
  \draw[fw] (nu) -- node[above=2pt,lab,black]{$\BZ$} (d);
  \draw[fw] (d) -- node[above=2pt,lab,black]{$A_0^{\Z}$} (9.0,0);
\end{tikzpicture}
\caption{A source $\mu$, an encoder $e$, a channel $\nu$ and a decoder $d$. Each box is a shift-equivariant
Markov kernel; the encoder and decoder are deterministic. Shannon's theorem asks when the composite
$d\circ\nu\circ e$ can be made close to the identity on $\mu$-typical inputs.}\label{fig:intro}
\end{figure}

\textbf{Part~I} is about entropy as a function. \Cref{ch:schemes} sets up finite schemes as a category and
shows that conditional entropy is the entropy of a morphism, so that the chain rule is functoriality.
\Cref{ch:uniqueness} proves Khinchin's uniqueness theorem and places it among its successors: Faddeev's
theorem, the functorial characterization of Baez, Fritz and Leinster, and the operadic one. \Cref{ch:cocycle}
develops information cohomology in a finite and explicit form. \Cref{ch:inequalities} treats Khinchin's
elementary inequalities through relative entropy and the data-processing inequality, which is the statement
that composition is short for a divergence.

\textbf{Part~II} is about sources. \Cref{ch:sources} constructs sequence spaces as infinite tensor products,
defines the entropy rate, and reads finite-state sources as coalgebras. \Cref{ch:ergodic} treats ergodicity
and the ergodic decomposition. \Cref{ch:martingales} is about conditional expectations as idempotents and
the convergence of martingales. \Cref{ch:aep} proves McMillan's theorem in mean from two soft convergence
statements and one elementary estimate.

\textbf{Part~III} is about channels. \Cref{ch:channels} defines channels with memory, repairs a gap in
Khinchin's treatment of ergodicity that was found soon after publication, and studies capacity as a
function on a monoidal category. \Cref{ch:feinstein} proves Feinstein's lemma in its one-shot form and
reads codes as approximate retractions. \Cref{ch:shannon} proves the coding theorems and their converses, and
shows the martingale returning as the engine of an explicit construction. \Cref{ch:rates} places entropy and
capacity among asymptotic invariants of preordered semirings.

\textbf{Part~IV}, \cref{ch:coda}, is an assessment and a list of open problems. The appendices contain the
categorical toolkit, a concordance with Khinchin's text, a description of the computational checks, and
solutions to all exercises.

\section*{A dictionary}

\begin{center}\small
\renewcommand{\arraystretch}{1.25}
\begin{tabular}{@{}p{0.40\textwidth}p{0.52\textwidth}@{}}
\toprule
\textbf{Khinchin} & \textbf{Here}\\\midrule
finite scheme & object of $\FinProb$; state $1\to X$ in $\FinStoch$\\
conditional entropy $H_A(B)$ & entropy of the projection $(A\times B,r)\to(A,p)$\\
$H(AB)=H(A)+H_A(B)$ & functoriality; the 1-cocycle condition\\
uniqueness theorem & $H^1\iso\R$; initiality of $\FinProb$\\
Shannon's inequality and its generalizations & positivity of relative entropy; submodularity\\
source $[A,\mu]$ & shift-invariant state on a Kolmogorov product\\
ergodic source & invariant state that is deterministic on the invariant $\sigma$-algebra\\
conditional probability given the past & dagger-split idempotent\\
the $E$ property & the block $A^n$ is an $\varepsilon$-retract of a set of $2^{nH}$ points\\
channel $[A,\nu_x,B]$ & equivariant Markov kernel $\AZ\to\BZ$\\
without anticipation & natural transformation of towers\\
connection of channel to source & composition after copying\\
distinguishable group of sequences & $\varepsilon$-retraction of the channel onto a finite set\\
ergodic capacity & asymptotic $\varepsilon$-rank\\
a code is a channel & deterministic morphisms are morphisms\\
\bottomrule
\end{tabular}
\end{center}

\section*{How to read the tags}

A reader who wants only the mathematics of information theory can read the statements tagged
\textsf{classical} and their proofs; they are complete in themselves. A reader who knows that mathematics
and wants the categorical account can read the statements tagged \textsf{literature} and
\textsf{reformulation}. The tags \textsf{observation} and \textsf{programme} mark where we are on our own:
the first for elementary remarks with proofs, the second for directions without them.
%% ---- end front.tex ----
\mainmatter
\part{Entropy}
%% ---- begin ch/01-schemes.tex ----
\chapter{Finite Schemes}\label{ch:schemes}

Khinchin's first paper begins with a \emph{finite scheme}: a complete system of mutually exclusive events
$A_1,\dots,A_n$ together with their probabilities $p_1,\dots,p_n$. He defines its entropy, lists the properties
of entropy that will be needed later, and observes that one of them, the rule for the entropy of a product
scheme, is the important one. This chapter does the same, with one change of emphasis. Finite schemes form
a category, and the important property says that entropy is a functor on it. The entropy of a scheme is the
value of that functor on a particular map.

\section{Schemes and their maps}

\begin{definition}\label{def:finprob}
A \term{finite probability space}, or finite scheme, is a pair $(X,p)$ of a finite set $X$ and a probability
distribution $p$ on it. A morphism $f\colon(X,p)\to(Y,q)$ is a map of sets with $f_*p=q$, that is,
$q(y)=\sum_{x\in f^{-1}(y)}p(x)$. These form the category $\FinProb$. The category $\FinStoch$ has finite
sets as objects and stochastic matrices as morphisms: a morphism $f\colon X\to Y$ is a family of
distributions $f(\,\cdot\st x)$ on $Y$, one for each $x\in X$, and
$(g\circ f)(z\st x)=\sum_yg(z\st y)f(y\st x)$.
\end{definition}

A distribution on $X$ is a morphism $1\to X$ in $\FinStoch$, a \term{state}. A map of sets is a stochastic
matrix with entries in $\{0,1\}$, so $\FinSet$ is a subcategory of $\FinStoch$, and a morphism of
$\FinProb$ is a map of sets that carries one state to another. We write $\Delta_n$ for the simplex of
distributions on $\{1,\dots,n\}$ and $u_n$ for the uniform one.

$\FinStoch$ is a symmetric monoidal category under the product of sets and the tensor product of
matrices, $(f\otimes g)(y,y'\st x,x')=f(y\st x)\,g(y'\st x')$. Each object has a copy map
$\cpy_X\colon X\to X\times X$ and a delete map $\del_X\colon X\to1$, both coming from $\FinSet$. These data
make it a \emph{Markov category} (\cref{app:toolkit}). A morphism $f$ is \term{deterministic} when it
commutes with copying, $\cpy_Y\circ f=(f\otimes f)\circ\cpy_X$; in $\FinStoch$ these are exactly the maps of
sets. A state is deterministic exactly when it is a point mass. We shall see in \cref{ch:inequalities} that
entropy measures by how much a state fails this equation.

Khinchin's product scheme $AB$ needs a comment. Given schemes $A$ and $B$ he considers the events $A_iB_k$
and their probabilities, which presupposes that $A$ and $B$ are defined on a common probability space. In
our terms there is a space $(\Omega,P)$ and two morphisms out of it,
\[ (X,p)\xleftarrow{\ a\ }(\Omega,P)\xrightarrow{\ b\ }(Y,q), \]
and $AB$ is the image of the pairing, a distribution $r$ on $X\times Y$ with marginals $p$ and $q$. It is the
product distribution $p\otimes q$ only when $A$ and $B$ are independent. \Cref{ch:cocycle} takes the common
space $\Omega$ as the basic datum.

\section{Entropy}

\begin{definition}\label{def:entropy}
The \term{entropy} of a distribution $p$ on a finite set $X$ is
\[ H(p)=-\sum_{x\in X}p(x)\log p(x), \]
with $0\log0=0$ and logarithms to base $2$.
\end{definition}

For a joint distribution $r$ on $X\times Y$ with marginals $p$ and $q$, write $r(\,\cdot\st x)$ for the
conditional distribution on $Y$ given $x$, defined when $p(x)>0$, and put
\[ H_A(B)=\sum_xp(x)\,H\bigl(r(\,\cdot\st x)\bigr). \]
This is Khinchin's conditional entropy of $B$ given $A$; the modern notation is $H(B\st A)$.

\begin{proposition}[Khinchin's properties]\label{prop:properties}
\Scl[\cite{Sha48,Khi53}]
\begin{enumerate}[label=(\roman*)]
\item $H(p)\ge0$, with equality iff $p$ is a point mass.
\item $H(p)\le\log|X|$, with equality iff $p$ is uniform.
\item $H(r)=H(p)+H_A(B)$.
\item $H_A(B)\le H(q)$, with equality iff $r=p\otimes q$. In particular $H(p\otimes q)=H(p)+H(q)$.
\end{enumerate}
\end{proposition}

\begin{proof}
Let $\varphi(t)=-t\log t$, a strictly concave function on $[0,1]$ vanishing at $0$ and $1$. (i) is clear.
(ii) By Jensen's inequality $\frac1n\sum_x\varphi(p(x))\le\varphi(\frac1n)$ with $n=|X|$. (iii) Write
$r(x,y)=p(x)\,r(y\st x)$ and take logarithms. (iv) Since $q(y)=\sum_xp(x)\,r(y\st x)$, Jensen's inequality gives
$\varphi(q(y))\ge\sum_xp(x)\,\varphi(r(y\st x))$ for each $y$; sum over $y$. Equality requires $r(y\st x)$ to be
independent of $x$.
\end{proof}

\begin{example}\label{ex:first}
For $p=(\tfrac12,\tfrac14,\tfrac18,\tfrac18)$ we have $H(p)=\tfrac12\cdot1+\tfrac14\cdot2+2\cdot\tfrac18\cdot3=1.75$ bits. A
uniform distribution on four points has $2$ bits. One can identify an outcome of $p$ by asking ``is it the
first?'', then ``is it the second?'', then ``is it the third?'', which takes $1$, $2$, $3$ or $3$
questions and $1.75$ on average.
\end{example}

\section{The entropy of a map}

Property (iii) is usually read as a rule for computing the entropy of a joint distribution. Read in
the other direction, it says what a difference of entropies is.

\begin{definition}\label{def:Hmap}
Let $f\colon(X,p)\to(Y,q)$ be a morphism of $\FinProb$. For $y$ with $q(y)>0$ let $p_y$ be $p$ conditioned on
the fibre $f^{-1}(y)$. The \term{entropy of $f$} is
\[ H(f)=\sum_yq(y)\,H(p_y). \]
\end{definition}

\begin{proposition}\label{prop:loss}
\Scl[the chain rule] $H(f)=H(p)-H(q)$.
\end{proposition}

\begin{proof}
For $x$ in the fibre over $y$ we have $p(x)=q(y)\,p_y(x)$, so
$-\sum_xp(x)\log p(x)=-\sum_yq(y)\log q(y)-\sum_yq(y)\sum_{x\in f^{-1}y}p_y(x)\log p_y(x)$.
\end{proof}

\begin{theorem}[Entropy is a functor]\label{thm:functor}
\Sli[\cite{BFL11}] Regard the additive monoid $[0,\infty)$ as a category with one object. Then $f\mapsto H(f)$
is a functor $\FinProb\to[0,\infty)$:
\[ H(g\circ f)=H(f)+H(g),\qquad H(\id)=0. \]
Moreover $H(f)=0$ iff $f$ is injective on the support of $p$.
\end{theorem}

\begin{proof}
By \cref{prop:loss} the sum telescopes. $H(f)=0$ iff each $p_y$ is a point mass.
\end{proof}

The entropy of an object is recovered as the entropy of its unique map to the one-point space,
$H(p)=H\bigl((X,p)\to1\bigr)$, and Khinchin's conditional entropy as the entropy of a projection,
$H_A(B)=H\bigl(\pi_X\colon(X\times Y,r)\to(X,p)\bigr)$. Property (iii) is then functoriality along
\[ (X\times Y,r)\xrightarrow{\ \pi_X\ }(X,p)\longrightarrow1. \]
So the statement Khinchin singles out as the essential property of entropy says that entropy is a functor,
and the definition of conditional entropy as an average over fibres says what that functor does to a map
that is not a projection to a point. $H(f)$ is the information lost by applying $f$; equivalently, it is the
average information needed to recover $x$ from $f(x)$.

\begin{example}\label{ex:coarse}
Let $p$ be as in \cref{ex:first}. The map $f$ that merges the last two outcomes has image
$q=(\tfrac12,\tfrac14,\tfrac14)$ with $H(q)=1.5$, so $H(f)=0.25$. Directly: only the fibre over the third
point is not a singleton, it has probability $\tfrac14$ and conditional distribution $(\tfrac12,\tfrac12)$, so
$H(f)=\tfrac14\cdot1$. The map $f'$ that merges the first two outcomes has $H(f')=\tfrac34\,\hb(\tfrac23)\approx0.689$.
Merging likely outcomes loses more.
\end{example}

\section{Mixtures and the operad of simplices}

For $q\in\Delta_m$ and $p_i\in\Delta_{k_i}$, $i=1,\dots,m$, define the composite
\[ q\circ(p_1,\dots,p_m)=(q_1p_{11},\dots,q_1p_{1k_1},\ \dots,\ q_mp_{m1},\dots,q_mp_{mk_m})\in\Delta_{k_1+\dots+k_m}. \]
This is the distribution of a two-stage experiment: choose $i$ according to $q$, then an outcome according
to $p_i$. Composition is associative and has the unit $u_1\in\Delta_1$, and permuting the entries of $q$
permutes blocks. The simplices therefore form a symmetric topological operad $\Delta=(\Delta_n)_{n\ge1}$
(\cref{app:toolkit}).

\begin{proposition}[Chain rule, operadic form]\label{prop:chainrule}
\Scl $H\bigl(q\circ(p_1,\dots,p_m)\bigr)=H(q)+\sum_{i=1}^mq_i\,H(p_i)$.
\end{proposition}

\begin{proof}
The composite is a distribution $p$ on a set mapping to $\{1,\dots,m\}$ with image $q$ and conditional
distributions $p_i$ on the fibres. Apply \cref{prop:loss}.
\end{proof}

Conversely every morphism $f\colon(X,p)\to(Y,q)$ exhibits $p$ as a composite $q\circ(p_y)_{y\in Y}$, up to the
order of the points. Morphisms of $\FinProb$ are operadic composites, and $H(f)=\sum_yq(y)H(p_y)$ is the second
term of the chain rule.

There is a second structure. For $\lambda\in[0,1]$ and two objects, let
$\lambda(X,p)\oplus(1-\lambda)(X',p')$ be the disjoint union $X\sqcup X'$ with the distribution
$\lambda p$ on $X$ and $(1-\lambda)p'$ on $X'$. The same formula on maps defines
$\lambda f\oplus(1-\lambda)f'$.

\begin{proposition}\label{prop:convexlinear}
\Sli[\cite{BFL11}] $H$ is convex-linear on morphisms:
\[ H\bigl(\lambda f\oplus(1-\lambda)f'\bigr)=\lambda H(f)+(1-\lambda)H(f'). \]
On objects, $H\bigl(\lambda p\oplus(1-\lambda)p'\bigr)=\lambda H(p)+(1-\lambda)H(p')+\hb(\lambda)$.
\end{proposition}

\begin{proof}
A fibre of $\lambda f\oplus(1-\lambda)f'$ is a fibre of $f$ or of $f'$, with the same conditional distribution
and with weight multiplied by $\lambda$ or $1-\lambda$. The second formula is \cref{prop:chainrule} for
$(\lambda,1-\lambda)\circ(p,p')$.
\end{proof}

The two statements do not conflict. The entropy of an object is the entropy of its map to $1$, and the
mixture of the maps $(X,p)\to1$ and $(X',p')\to1$ is a map to the two-point space with distribution
$(\lambda,1-\lambda)$, not to $1$. The term $\hb(\lambda)$ is the entropy of the remaining map to $1$. A
function on objects that is not affine comes from a function on morphisms that is.

\section{Kernels, noise and equivocation}

Let $f\colon X\to Y$ be a morphism of $\FinStoch$ and $p$ a state on $X$. The joint distribution
$r(x,y)=p(x)f(y\st x)$ on $X\times Y$ has marginals $p$ and $q=f\circ p$. Its two conditional entropies have
names:
\begin{align*}
 H(Y\st X)&=\sum_xp(x)\,H\bigl(f(\,\cdot\st x)\bigr)&&\text{(noise)},\\
 H(X\st Y)&=H(\pi_Y)&&\text{(equivocation)}.
\end{align*}
The \term{mutual information} is $I(X;Y)=H(p)+H(q)-H(r)=H(q)-H(Y\st X)=H(p)-H(X\st Y)$. By
\cref{prop:properties}(iv) it is nonnegative and vanishes iff $r=p\otimes q$.

When $q$ has full support there is a unique kernel $f^\dagger\colon Y\to X$ with
\[ p(x)\,f(y\st x)=q(y)\,f^\dagger(x\st y), \]
the \term{Bayesian inverse} of $f$ with respect to $p$. Noise and equivocation are exchanged by
$f\mapsto f^\dagger$. If $f$ is a map of sets its noise is zero and its Bayesian inverse is
$f^\dagger(\,\cdot\st y)=p_y$, so that
\[ H(f)=\sum_yq(y)\,H\bigl(f^\dagger(\,\cdot\st y)\bigr). \]

\begin{proposition}\label{prop:lossnoise}
\Srf[\cite{BF14,FuP21}] The entropy of a morphism of $\FinProb$ is the noise of its Bayesian inverse. For a
general kernel $f$ and state $p$,
\[ H(X\st Y)=H(p)-H(q)+H(Y\st X). \]
\end{proposition}

So the functor of \cref{thm:functor} is the restriction to deterministic maps of the equivocation, which is
defined for all kernels. The equivocation is not additive under composition of kernels, only subadditive
(\cref{exer:triangle}); it becomes additive on maps because their noise is zero. This is the first
appearance of a pattern that will recur. A statement that is an equality for deterministic morphisms
weakens to an inequality for stochastic ones, and the inequality is the useful part.

\section*{Notes}

Entropy and its properties are due to Shannon \cite{Sha48}; Khinchin's account is \cite[\S1]{Khi53}. Categories
of probability spaces and stochastic maps go back to Lawvere \cite{Law62}, \v{C}encov \cite{Cen82} and Giry
\cite{Gir82}. Markov categories were introduced by Cho and Jacobs \cite{CJ19} and Fritz \cite{Fri20}. The
observation that entropy is naturally a function of a morphism, and \cref{thm:functor}, are due to Baez,
Fritz and Leinster \cite{BFL11}; the operad of simplices and its role are developed in Leinster's book
\cite{Lei21}. The extension of the information-loss functor to stochastic maps is studied by Fullwood and
Parzygnat \cite{FuP21}.

\section*{Exercises}

\begin{exercise}
For $p=(\tfrac12,\tfrac14,\tfrac18,\tfrac18)$, let $g$ merge the first two outcomes and then $h$ merge the
two remaining light outcomes. Compute $H(g)$, $H(h)$ and $H(h\circ g)$, and check \cref{thm:functor}.
\end{exercise}

\begin{exercise}
Show that $H(f)=H(p)$ iff $f_*p$ is a point mass, and that isomorphic objects of $\FinProb$ have the same
entropy. Is the converse true?
\end{exercise}

\begin{exercise}\label{exer:grouping}
Let $p\in\Delta_n$ with $p_1=t$. Show that $H(p)\le\hb(t)+(1-t)\log(n-1)$, with equality iff the remaining
mass is spread uniformly.
\end{exercise}

\begin{exercise}\label{exer:doubly}
Let $W$ be a stochastic matrix from a finite set $X$ to itself. Show that $H(W\circ p)\ge H(p)$ for every
state $p$ if and only if $W$ is doubly stochastic. (For the direct implication you may use that a doubly
stochastic matrix is a convex combination of permutation matrices.)
\end{exercise}

\begin{exercise}\label{exer:triangle}
Let $X\to Y\to Z$ be composable kernels with a state on $X$. Show that
$H(X\st Z)\le H(X\st Y)+H(Y\st Z)$, with equality when both kernels are deterministic. Give an example of
strict inequality.
\end{exercise}
%% ---- end ch/01-schemes.tex ----
%% ---- begin ch/02-uniqueness.tex ----
\chapter{The Uniqueness Theorem}\label{ch:uniqueness}

Shannon remarked that his formula for entropy is forced by a few natural requirements, and gave an argument.
Khinchin's first paper turned the remark into a theorem with a complete proof, and Faddeev sharpened it
three years later. The result has been reproved and reformulated many times since. This chapter proves
Khinchin's version, states its main descendants, and asks which hypothesis does what. The answer prepares
\cref{ch:cocycle}: the hypothesis that matters is a cocycle condition, and the others are regularity.

\section{Khinchin's theorem}

Let $H$ assign a real number to each $p\in\Delta_n$ for every $n\ge1$. We assume throughout that $H$ is
symmetric, that is, invariant under permutations of $p_1,\dots,p_n$; Khinchin does not state this, but it
is implicit in his treating $H$ as a function of the scheme. Consider the conditions:
\begin{enumerate}[label=(K\arabic*)]
\item for each $n$, $H$ is largest at the uniform distribution $u_n$;
\item for every joint distribution $r$ on $X\times Y$ with first marginal $p$,
$H(r)=H(p)+\sum_xp(x)H\bigl(r(\,\cdot\st x)\bigr)$;
\item $H(p_1,\dots,p_n,0)=H(p_1,\dots,p_n)$.
\end{enumerate}

\begin{theorem}[Khinchin]\label{thm:khinchin}
\Scl[\cite{Khi53}] If $H$ is continuous on each $\Delta_n$ and satisfies \textup{(K1)--(K3)}, then there is a
constant $\lambda\ge0$ with
\[ H(p)=-\lambda\sum_ip_i\log p_i. \]
\end{theorem}

Khinchin says that $\lambda$ is positive. The zero function satisfies the hypotheses, so $\lambda=0$ must be
allowed.

\begin{lemma}\label{lem:monotone}
\Scl Let $L\colon\{1,2,\dots\}\to\R$ be nondecreasing with $L(mn)=L(m)+L(n)$. Then $L(n)=\lambda\log n$ with
$\lambda=L(2)\ge0$.
\end{lemma}

\begin{proof}
$L(1)=0$, so $L\ge0$. Fix $n\ge2$ and $k\ge1$ and choose $m$ with $2^m\le n^k<2^{m+1}$. Monotonicity and
additivity give $mL(2)\le kL(n)\le(m+1)L(2)$, and also $m\le k\log n<m+1$. If $L(2)=0$ then $L(n)=0$. Otherwise
$|L(n)/L(2)-\log n|\le1/k$ for every $k$.
\end{proof}

\begin{proof}[Proof of \cref{thm:khinchin}]
Put $L(n)=H(u_n)$. By (K3) and (K1), $L(n)=H(\tfrac1n,\dots,\tfrac1n,0)\le L(n+1)$. Apply (K2) to the product of
$u_m$ and $u_n$: every conditional distribution is $u_n$, so $L(mn)=L(m)+L(n)$. By \cref{lem:monotone},
$L(n)=\lambda\log n$.

Now let $p$ have rational entries $p_i=g_i/g$ with positive integers $g_i$ summing to $g$. Let $Y$ be a set
of $g$ points divided into blocks of sizes $g_1,\dots,g_n$, and let $r$ be the joint distribution on
$\{1,\dots,n\}\times Y$ under which $i$ has distribution $p$ and, given $i$, the second coordinate is
uniform on the $i$-th block. Then $r$ is uniform on $g$ pairs and zero elsewhere, so $H(r)=L(g)$ by (K3)
and symmetry. Each conditional distribution is uniform on $g_i$ points, so (K2) reads
$L(g)=H(p)+\sum_ip_iL(g_i)$, that is,
\[ H(p)=\lambda\sum_ip_i(\log g-\log g_i)=-\lambda\sum_ip_i\log p_i. \]
Rational points with positive entries are dense in $\Delta_n$ and $H$ is continuous.
\end{proof}

The proof has two steps of different character. The second, which passes from uniform distributions to all
rational ones, uses only (K2) and (K3) and is pure algebra. The first, which determines $L$, is where a
regularity hypothesis is needed, and (K1) is used there and nowhere else. It supplies the monotonicity
that makes \cref{lem:monotone} a three-line argument.

\section{Faddeev's theorem and the operadic form}

Faddeev showed that (K1) can be dropped and (K2) weakened to its simplest instance.

\begin{theorem}[Faddeev]\label{thm:faddeev}
\Scl[\cite{Fad56}] Let $H$ be symmetric, with $H(t,1-t)$ continuous in $t$, and suppose that whenever
$p_n=q_1+q_2>0$,
\[ H(p_1,\dots,p_{n-1},q_1,q_2)=H(p_1,\dots,p_n)+p_n\,H\Bigl(\frac{q_1}{p_n},\frac{q_2}{p_n}\Bigr). \]
Then $H(p)=-\lambda\sum_ip_i\log p_i$ for a real constant $\lambda$.
\end{theorem}

The displayed condition is called recursivity. By induction it implies the chain rule of
\cref{prop:chainrule} in full (\cref{exer:recursive}), and expansibility (K3) follows by taking $q_2=0$. The
price of dropping (K1) is that $L(n)=H(u_n)$ is no longer known to be monotone. Faddeev replaces
\cref{lem:monotone} by a harder statement about additive arithmetic functions, in the spirit of a theorem
of Erd\H{o}s \cite{Erd46}:

\begin{lemma}\label{lem:faddeev}
\Scl[\cite{Fad56,Ren61}] If $a(mn)=a(m)+a(n)$ for all $m,n\ge1$ and $a(n+1)-\frac{n}{n+1}a(n)\to0$, then
$a(n)=c\log n$.
\end{lemma}

In the operadic language of \cref{ch:schemes} the theorem takes its cleanest form. Symmetry need not be
assumed.

\begin{theorem}[Faddeev--Leinster]\label{thm:FL}
\Sli[\cite{Lei21}, Thm.~2.5.1] Let $I=(I_n\colon\Delta_n\to\R)_{n\ge1}$ be a sequence of functions. The
following are equivalent:
\begin{enumerate}[label=(\roman*)]
\item each $I_n$ is continuous and $I\bigl(q\circ(p_1,\dots,p_m)\bigr)=I(q)+\sum_iq_iI(p_i)$ for all composable
$q,p_1,\dots,p_m$;
\item $I=cH$ for some $c\in\R$.
\end{enumerate}
\end{theorem}

\begin{proof}[Proof sketch]
Assume (i). From $u_1\circ(u_1)=u_1$ we get $I(u_1)=0$. From
$(1,0)\circ\bigl((1,0),u_1\bigr)=(1,0,0)=(1,0)\circ\bigl(u_1,(1,0)\bigr)$ we get $I(1,0)+I(1,0)=I(1,0)$, so
$I(1,0)=0$. Since $u_m\circ(u_n,\dots,u_n)=u_{mn}$, the sequence $a(n)=I(u_n)$ is additive. Since
$u_{n+1}=(\tfrac{n}{n+1},\tfrac1{n+1})\circ(u_n,u_1)$,
\[ a(n+1)-\tfrac{n}{n+1}\,a(n)=I\bigl(\tfrac{n}{n+1},\tfrac1{n+1}\bigr)\longrightarrow I(1,0)=0 \]
by continuity. \Cref{lem:faddeev} gives $a(n)=c\log n$. For rational $p$ with $p_i=g_i/g$ we have
$p\circ(u_{g_1},\dots,u_{g_n})=u_g$, so $I(p)=a(g)-\sum_ip_ia(g_i)=cH(p)$, and continuity finishes the proof.
\end{proof}

The identity $p\circ(u_{g_1},\dots,u_{g_n})=u_g$ is Khinchin's auxiliary scheme $B$. His proof and this one
are the same after the determination of $L$.

\section{The functorial characterization}

\Cref{thm:functor,prop:convexlinear} say that entropy is a convex-linear functor. Baez, Fritz and Leinster
showed that this characterizes it. Call a functor $F\colon\FinProb\to[0,\infty)$ \term{continuous} if
$F(f_k)\to F(f)$ whenever $f_k\colon(X,p_k)\to(Y,q_k)$ have the same underlying map as $f\colon(X,p)\to(Y,q)$
and $p_k\to p$.

\begin{theorem}[Baez--Fritz--Leinster]\label{thm:BFL}
\Sli[\cite{BFL11}] Let $F\colon\FinProb\to[0,\infty)$ be a functor that is convex-linear and continuous. Then
there is a constant $c\ge0$ such that for every $f\colon(X,p)\to(Y,q)$,
\[ F(f)=c\,\bigl(H(p)-H(q)\bigr). \]
\end{theorem}

\begin{proof}
For an object $(X,p)$ let $I(p)=F\bigl((X,p)\to1\bigr)$. Functoriality along $(X,p)\to(Y,q)\to1$ gives
$F(f)=I(p)-I(q)$. An isomorphism $\phi$ has $F(\phi)+F(\phi^{-1})=0$ with both terms nonnegative, so $I$ is
invariant under relabelling. Now let $p=q\circ(p_1,\dots,p_m)$ and let $f$ be the corresponding map to
$(\{1,\dots,m\},q)$. It is the convex combination, with weights $q_i$, of the maps from the $i$-th block to a
point, so convex-linearity gives $F(f)=\sum_iq_iI(p_i)$. Hence $I(p)=I(q)+\sum_iq_iI(p_i)$. $I$ is
continuous, so $I=cH$ by \cref{thm:FL}, and $c\ge0$ because $F\ge0$.
\end{proof}

Three things have changed relative to Khinchin's formulation. Nothing is assumed about maxima.
Symmetry is not an axiom; it is the fact that functors send isomorphisms to invertible elements. And
expansibility has disappeared, because adjoining an outcome of probability zero is an isomorphism in
$\FinProb$ once morphisms are taken up to null sets, or else follows from the chain rule as in
\cref{thm:faddeev}. What remains is the chain rule in two halves, functoriality and convex-linearity, and
continuity.

\section{Entropy as a derivation}

There is one more way to write the chain rule. For $p\in\Delta_n$, $q\in\Delta_k$ and $1\le i\le n$ let
$p\circ_iq\in\Delta_{n+k-1}$ be the result of replacing the $i$-th outcome of $p$ by a copy of $q$ scaled by
$p_i$. The full composite is an iterated partial composite, and the chain rule is equivalent to
\begin{equation}\label{eq:leibniz}
 H(p\circ_iq)=H(p)+p_i\,H(q).
\end{equation}
Let the operad $\Delta$ act on $\R$ on the left by $p\cdot_ir=p_ir$ and on the right trivially. Then
\eqref{eq:leibniz} is the Leibniz rule $d(p\circ_iq)=dp\cdot q+p\cdot_i dq$.

\begin{theorem}\label{thm:derivation}
\Sli[\cite{Bra21,Lei21}] Entropy is a derivation of the operad of simplices with values in $\R$, and every
continuous derivation is a real multiple of it.
\end{theorem}

The first statement is due to Bradley, who also gives a pointwise form of the converse; the second as
stated here is \cref{thm:FL}. Leinster proves a categorified version: $\FinProb$ is the free categorical
algebra for $\Delta$ containing an internal algebra, and the internal algebras in the one-object category
$(\R,+)$ are the multiples of entropy \cite[Ch.~12]{Lei21}, from which \cref{thm:BFL} follows.

A derivation is a 1-cocycle in Hochschild cohomology, and one expects a cohomology theory in which entropy
is a class. The next chapter constructs it, for a monoid in place of the operad.

\section{What the chain rule excludes}

How much of the theorem is due to the conditional form of (K2)? For $\alpha>0$, $\alpha\ne1$, the
\term{R\'enyi entropy} of order $\alpha$ is
\[ H_\alpha(p)=\frac{1}{1-\alpha}\log\sum_ip_i^\alpha. \]
It is continuous and symmetric, it satisfies (K1) and (K3), and it is additive on independent products,
$H_\alpha(p\otimes q)=H_\alpha(p)+H_\alpha(q)$. As $\alpha\to1$ it tends to $H(p)$; as $\alpha\to0$ it tends to
the \term{Hartley entropy} $\log|\supp p|$, and as $\alpha\to\infty$ to the min-entropy $-\log\max_ip_i$.

\begin{example}\label{ex:renyi}
Take $p=(\tfrac12,\tfrac14,\tfrac14)=(\tfrac12,\tfrac12)\circ(u_1,u_2)$. Then
$H_2(p)=-\log(\tfrac14+\tfrac1{16}+\tfrac1{16})=\log\tfrac83\approx1.415$, while the chain rule would predict
$H_2(\tfrac12,\tfrac12)+\tfrac12H_2(u_2)=1.5$.
\end{example}

So among Khinchin's hypotheses, everything except the conditional additivity (K2) for dependent schemes is
satisfied by a one-parameter family. The chain rule is the hypothesis with content, and it is strong: it
fixes the function up to a scalar. \Cref{ch:rates} returns to the R\'enyi family, which reappears when
coding is required to be exact.

Regularity cannot be dropped altogether. If $\ell\colon(0,1]\to\R$ satisfies $\ell(xy)=\ell(x)+\ell(y)$, then
$p\mapsto-\sum_ip_i\ell(p_i)$ satisfies the chain rule, by the same computation as for the logarithm. Using
the axiom of choice one can take $\ell=A\circ\log$ with $A$ a discontinuous additive function, and the result
is not a multiple of entropy. Measurability is enough to exclude this \cite{Lee64}.

\section*{Notes}

Shannon's axiomatic remark is in \cite[\S6]{Sha48}; Khinchin's theorem is \cite[\S2]{Khi53}. Faddeev's
theorem is \cite{Fad56}; R\'enyi \cite{Ren61} simplified the proof and introduced the entropies named
after him. The monograph of Acz\'el and Dar\'oczy \cite{AD75} surveys the functional-equation literature.
The functorial characterization is \cite{BFL11}; the operadic and categorical-algebra viewpoint is in
\cite{Lei21}, and the derivation viewpoint in \cite{Bra21}. Parzygnat \cite{Par22} gives a functorial
characterization of von Neumann entropy in the same spirit.

\section*{Exercises}

\begin{exercise}
Carry out the second step of Khinchin's proof for $p=(\tfrac12,\tfrac13,\tfrac16)$: describe the joint
distribution $r$, and verify numerically that $\log g-\sum_ip_i\log g_i=H(p)$.
\end{exercise}

\begin{exercise}\label{exer:recursive}
Show that symmetry and Faddeev's recursivity imply $H(p\circ_iq)=H(p)+p_iH(q)$ for all $q\in\Delta_k$, by
induction on $k$, and deduce the full chain rule.
\end{exercise}

\begin{exercise}
Show that $H_\alpha$ is additive on products and satisfies \textup{(K1)} and \textup{(K3)}. Compute
$\lim_{\alpha\to1}H_\alpha(p)$.
\end{exercise}

\begin{exercise}\label{exer:renyifunctor}
Any function $I$ on objects of $\FinProb$ that is invariant under isomorphism defines a functor to $(\R,+)$
by $F(f)=I(p)-I(q)$. Show that for $I=H_2$ this functor is continuous and takes values in $[0,\infty)$, and
exhibit a failure of convex-linearity. Which step of the proof of \cref{thm:BFL} breaks?
\end{exercise}

\begin{exercise}
Let $I$ satisfy \eqref{eq:leibniz} for all $p$, $q$ and $i$. Show that $I(u_1)=0$, that $I(1,0)=0$, and that
$I$ satisfies the full chain rule.
\end{exercise}
%% ---- end ch/02-uniqueness.tex ----
%% ---- begin ch/03-cocycle.tex ----
\chapter{Entropy as a Cocycle}\label{ch:cocycle}

The chain rule $H(AB)=H(A)+H_A(B)$ has the shape of a cocycle condition: the value on a product is the value
on the first factor plus the value on the second, transported by the first. Baudot and Bennequin made this
precise. Observables form a monoid, the monoid acts on functions of probability laws by conditioning, and
entropy is a 1-cocycle for this action. The uniqueness theorem becomes the computation of a cohomology
group. This chapter develops the theory in the simplest setting in which it is nontrivial, a finite sample
space with all its partitions, where everything can be done by hand.

\section{Observables}

Let $\Omega$ be a finite set. An \term{observable} is a partition $X$ of $\Omega$; one thinks of the quotient
map $\Omega\to\Omega/X$ as a random variable, and of two random variables as the same observable when each is
a function of the other. Say that $X$ \term{refines} $Y$ if every block of $X$ lies in a block of $Y$, so that
$Y$ is a function of $X$. The \term{product} $XY$ is the coarsest common refinement, whose blocks are the
nonempty intersections $B\cap C$ of a block of $X$ with a block of $Y$; it is the observable ``$X$ and $Y$
jointly''. The trivial partition $1$ is a unit. Under this product the set $\Pi(\Omega)$ of observables is a
commutative monoid in which every element is idempotent:
\[ XY=YX,\qquad XX=X,\qquad 1X=X. \]
$X$ refines $Y$ iff $XY=X$.

\begin{figure}[ht]\centering
\begin{tikzpicture}[x=1cm,y=1cm]
  \node (top) at (0,2.4) {$a\,|\,b\,|\,c$};
  \node (ya) at (-2.6,1.2) {$a\,|\,bc$};
  \node (yb) at (0,1.2) {$b\,|\,ac$};
  \node (yc) at (2.6,1.2) {$c\,|\,ab$};
  \node (one) at (0,0) {$abc$};
  \draw[thick] (top) -- (ya) -- (one) -- (yc) -- (top);
  \draw[thick] (top) -- (yb) -- (one);
  \node[lab,ink2] at (-3.6,1.2) {$Y_a$};
  \node[lab,ink2] at (0.9,1.2) {$Y_b$};
  \node[lab,ink2] at (3.6,1.2) {$Y_c$};
  \node[lab,ink2] at (0.7,0) {$1$};
\end{tikzpicture}
\caption{The five observables on a three-point set, ordered by refinement. The product of any two of the
binary observables $Y_a,Y_b,Y_c$ is the atomic observable at the top. This is the smallest structure on
which the chain rule has content, and \cref{thm:H1} is proved by reduction to it.}\label{fig:three}
\end{figure}

A \term{law} is a probability measure $P$ on $\Omega$. The law of an observable $X$ under $P$ is the
distribution $X_*P$ on the set of blocks of $X$. For a block $B$ with $P(B)>0$ we write $P|_B$ for the
conditional law.

\section{The conditioning action}

Let $\Fun$ be the vector space of measurable real functions on the simplex $\Delta(\Omega)$ of laws. For an
observable $Y$ and $f\in\Fun$ define
\begin{equation}\label{eq:action}
 (Y.f)(P)=\sum_{B\in Y,\ P(B)>0}P(B)\,f\bigl(P|_B\bigr).
\end{equation}
This is the average of $f$ after $Y$ has been observed.

\begin{lemma}\label{lem:action}
\Sli[\cite{BB15}] Formula \eqref{eq:action} is an action of the monoid $\Pi(\Omega)$ on $\Fun$: $1.f=f$ and
$Y.(Z.f)=(YZ).f$.
\end{lemma}

\begin{proof}
$(Y.(Z.f))(P)=\sum_BP(B)\sum_CP|_B(C)\,f\bigl((P|_B)|_C\bigr)=\sum_{B,C}P(B\cap C)\,f\bigl(P|_{B\cap C}\bigr)$, the sums being over
blocks with positive probability.
\end{proof}

Call $f\in\Fun$ \term{$X$-local} if $f(P)$ depends only on the law $X_*P$ of $X$, and write $\Fun_X$ for the
space of such functions. A function that is local for an observable is local for every refinement of it.
If $f$ is $Z$-local then $Y.f$ is $YZ$-local, because the law of $YZ$ determines the probabilities of the
blocks of $Y$ and the law of $Z$ under each conditional law.

\section{The complex}

\begin{definition}\label{def:complex}
An \term{$n$-cochain} is a family $f=\bigl(f[Y_1|\cdots|Y_n]\bigr)$, indexed by $n$-tuples of observables, with
$f[Y_1|\cdots|Y_n]\in\Fun_{Y_1\cdots Y_n}$. The coboundary of $f$ is the $(n+1)$-cochain
\begin{align*}
(\delta f)[Y_1|\cdots|Y_{n+1}]={}&Y_1.f[Y_2|\cdots|Y_{n+1}]
 +\sum_{k=1}^n(-1)^kf[Y_1|\cdots|Y_kY_{k+1}|\cdots|Y_{n+1}]\\
 &+(-1)^{n+1}f[Y_1|\cdots|Y_n].
\end{align*}
The cohomology of the complex $(C^\bullet,\delta)$ is the \term{information cohomology} $H^\bullet(\Omega)$ of
the full structure on $\Omega$.
\end{definition}

This is the standard complex computing the cohomology of a monoid with coefficients in a module, cut down
by the locality condition. That $\delta\delta=0$ is the usual computation, using \cref{lem:action}, and the
remark on locality shows that $\delta$ preserves the condition. A $0$-cochain is a function local for the
trivial observable, that is, a constant, so $C^0=\R$.

In low degrees, for a constant $c$ and a 1-cochain $f$,
\[ (\delta c)[Y]=Y.c-c=0,\qquad (\delta f)[Y|Z]=Y.f[Z]-f[YZ]+f[Y]. \]
The first vanishes because $\sum_BP(B)=1$. Thus $H^0(\Omega)=\R$, there are no nonzero 1-coboundaries, and a
1-cochain is a cocycle exactly when
\begin{equation}\label{eq:cocycle}
 f[YZ]=f[Y]+Y.f[Z]\qquad\text{for all observables $Y,Z$.}
\end{equation}

\begin{proposition}\label{prop:Hcocycle}
\Sli[\cite{BB15}] The family $H[Y](P)=H(Y_*P)$ is a 1-cocycle.
\end{proposition}

\begin{proof}
It is local by definition, and \eqref{eq:cocycle} for it is \cref{prop:properties}(iii) applied to the joint law
of $Y$ and $Z$: the term $(Y.H[Z])(P)=\sum_BP(B)\,H\bigl(Z_*(P|_B)\bigr)$ is Khinchin's $H_Y(Z)$.
\end{proof}

So Khinchin's property~2 is literally the cocycle condition. Two features of the formalism deserve notice
before we compute. The cocycle condition is imposed for a fixed sample space and all pairs of observables
on it, whereas Khinchin's theorem quantifies over all finite schemes; we shall see that three points
suffice. And since $YZ=ZY$, a cocycle satisfies
\begin{equation}\label{eq:symm}
 f[Y]+Y.f[Z]=f[Z]+Z.f[Y],
\end{equation}
which is a nontrivial constraint relating the values on $Y$ and on $Z$. Symmetry of entropy in its
arguments, an axiom in \cref{ch:uniqueness}, will come out of the commutativity of the monoid.

\section{The fundamental equation}

\begin{theorem}[Tverberg, Kendall, Lee]\label{thm:FEITH}
\Scl[\cite{Tve58,Ken64,Lee64}; see \cite{AD75}] Let $h\colon[0,1]\to\R$ be measurable with $h(1)=0$, and
suppose that
\begin{equation}\label{eq:FEITH}
 h(x)+(1-x)\,h\Bigl(\frac{y}{1-x}\Bigr)=h(y)+(1-y)\,h\Bigl(\frac{x}{1-y}\Bigr)
\end{equation}
for all $x,y\in[0,1)$ with $x+y\le1$. Then $h=c\,\hb$ for a constant $c$, where
$\hb(x)=-x\log x-(1-x)\log(1-x)$.
\end{theorem}

Equation \eqref{eq:FEITH} is called the fundamental equation of information theory. The condition
$h(1)=0$ cannot be omitted, since $h(x)=x$ is a solution. The binary entropy satisfies the equation because
both sides compute $H(x,y,1-x-y)$, by splitting off first one outcome and then the other.

\begin{theorem}\label{thm:H1}
\Sli[\cite{BB15,Vig20}; in this form proved here] Let $|\Omega|\ge3$. Every 1-cocycle is a constant multiple of
entropy. Hence
\[ H^0(\Omega)\iso\R,\qquad H^1(\Omega)\iso\R\cdot[H]. \]
\end{theorem}

\begin{proof}
Let $f$ be a 1-cocycle.

\emph{Step 0: normalization.} Taking $Y=Z$ in \eqref{eq:cocycle} and using $YY=Y$ gives $Y.f[Y]=0$, that is,
$\sum_BP(B)\,f[Y](P|_B)=0$ for all $P$. Under $P|_B$ the observable $Y$ is constant, so by locality
$f[Y](P|_B)$ is a number $c_B$ depending only on $B$. Then $\sum_BP(B)c_B=0$ for all $P$ forces $c_B=0$: a
cocycle vanishes at laws under which its argument is deterministic. In particular $f[1]=0$.

\emph{Step 1: three points.} Let $\Omega=\{a,b,c\}$ and let $Y_a$ be the partition $\{a\}\,|\,\{b,c\}$, and
similarly $Y_b,Y_c$. By locality $f[Y_a](P)=h_a(P(a))$ for a measurable function $h_a$ on $[0,1]$, and by
Step~0, $h_a(0)=h_a(1)=0$. Evaluate \eqref{eq:symm} for $Y_a,Y_c$ at the law $P=(x,1-x-y,y)$. Conditioning on
$\{a\}$ makes $Y_c$ deterministic; conditioning on $\{b,c\}$ gives $c$ the probability $y/(1-x)$. So
\[ h_a(x)+(1-x)\,h_c\Bigl(\frac{y}{1-x}\Bigr)=h_c(y)+(1-y)\,h_a\Bigl(\frac{x}{1-y}\Bigr). \]
Putting $y=1-x$ gives $h_a(x)=h_c(1-x)$. The same argument for the other two pairs gives
$h_a(x)=h_b(1-x)$ and $h_b(x)=h_c(1-x)$. Hence $h_a=h_b=h_c=h$ with $h(x)=h(1-x)$, and $h$ satisfies
\eqref{eq:FEITH}. By \cref{thm:FEITH}, $h=c\,\hb$, so $f[Y]=cH[Y]$ for the three binary observables. The
atomic observable is $Y_aY_c$, and \eqref{eq:cocycle} gives $f[Y_aY_c]=c\,(H[Y_a]+Y_a.H[Y_c])=cH[Y_aY_c]$.

\emph{Step 2: the general case.} Let $W$ be a partition of $\Omega$ into three blocks. The observables
refined by $W$, with the laws of $W$, form a copy of the three-point structure, because all the functions
involved are $W$-local and every distribution on three points is the law of $W$ under some $P$. So there is
a constant $c_W$ with $f[Y]=c_WH[Y]$ for every $Y$ refined by $W$. If two such partitions $W,W'$ both refine
a binary observable $Y$, then $c_W=c_{W'}$, since $H[Y]\ne0$. Any two binary observables $\{A,A^c\}$ and
$\{B,B^c\}$ are connected in this way: if the two are nested, say $A\subsetneq B$, both are refined by
$\{A,B\setminus A,B^c\}$; otherwise $A\cap B$ is a proper nonempty subset of both $A$ and $B$ and
$\{A\cap B,(A\cap B)^c\}$ is nested with each. Since $|\Omega|\ge3$, every binary observable is refined by
some $W$. Therefore $f[Y]=cH[Y]$ for all binary $Y$ with one constant $c$. Finally an observable with blocks
$B_1,\dots,B_k$ is the product of the binary observables $\{B_j,B_j^c\}$, and \eqref{eq:cocycle} determines the
value of a cocycle on a product from its values on the factors. Since $f$ and $cH$ agree on binary
observables, they agree everywhere.
\end{proof}

\begin{remark}
The hypothesis $|\Omega|\ge3$ is necessary. For $|\Omega|=2$ there is one nontrivial observable $X$, the only
cocycle conditions are $f[1]=0$ and $X.f[X]=0$, and $Z^1$ is the infinite-dimensional space of measurable
functions on $[0,1]$ vanishing at the endpoints (\cref{exer:two}). The chain rule constrains a function only
when there are two different observables to chain.
\end{remark}

Compare the hypotheses with those of \cref{thm:khinchin}. Continuity has been weakened to measurability. The
maximum property (K1) and expansibility (K3) are not assumed. Symmetry is not assumed; it was derived in
Step~1 from $YZ=ZY$. What is assumed is locality, which says that the quantity attached to an observable
depends only on its law, and the cocycle condition.

\section{Deformation}

For $\alpha>0$ replace \eqref{eq:action} by
\[ (Y._\alpha f)(P)=\sum_{B\in Y,\ P(B)>0}P(B)^\alpha f\bigl(P|_B\bigr). \]
The proof of \cref{lem:action} goes through, since $P(B)^\alpha\,P|_B(C)^\alpha=P(B\cap C)^\alpha$. Let $\delta_\alpha$ be
the coboundary built from this action and $H^\bullet_\alpha(\Omega)$ its cohomology. A constant is no longer
invariant:
\[ (\delta_\alpha c)[Y](P)=c\,\Bigl(\sum_BP(B)^\alpha-1\Bigr). \]

\begin{theorem}\label{thm:tsallis}
\Sli[\cite{Vig20}; cf.\ \cite{Dar70}] For $\alpha\ne1$ the \term{Tsallis entropy}
\[ S_\alpha[Y](P)=\frac{1}{\alpha-1}\Bigl(1-\sum_{B\in Y}P(B)^\alpha\Bigr) \]
is the coboundary of the constant $-1/(\alpha-1)$, hence a 1-cocycle for the $\alpha$-action:
$S_\alpha[YZ]=S_\alpha[Y]+Y._\alpha S_\alpha[Z]$. For $|\Omega|\ge3$ every measurable $\alpha$-cocycle is a multiple of it,
so that $H^0_\alpha(\Omega)=0$ and $H^1_\alpha(\Omega)=0$.
\end{theorem}

As $\alpha\to1$ the coboundary $\delta_\alpha1$ tends to zero and $S_\alpha$ tends to entropy measured in natural
units, $-\sum_BP(B)\ln P(B)$. This has a general explanation.

\begin{proposition}[Entropy as an obstruction]\label{prop:obstruction}
\Sob Let $\delta_\alpha$ be a family of differentials on a fixed graded vector space, differentiable in
$\alpha$, and write $\delta'$ for the derivative at $\alpha=1$. If $\delta_1c=0$, then $\delta'c$ is a
$\delta_1$-cocycle, and its class in cohomology vanishes iff $c$ extends to first order to a family of
cocycles $c+(\alpha-1)c'$. For the conditioning actions and $c=1$,
\[ \delta'1=-\ln2\cdot H, \]
so the class of entropy in $H^1(\Omega)$ is the obstruction to deforming the invariant constant $1$ along
the family of $\alpha$-actions.
\end{proposition}

\begin{proof}
Differentiating $\delta_\alpha\delta_\alpha=0$ at $\alpha=1$ gives $\delta'\delta_1+\delta_1\delta'=0$, so
$\delta_1(\delta'c)=-\delta'(\delta_1c)=0$. The family $c+(\alpha-1)c'$ is closed to first order iff
$\delta'c+\delta_1c'=0$. Finally $\frac{d}{d\alpha}\sum_BP(B)^\alpha\big|_{\alpha=1}=\sum_BP(B)\ln P(B)$.
\end{proof}

The dimensions fit: $(\dim H^0_\alpha,\dim H^1_\alpha)$ is $(0,0)$ for $\alpha\ne1$ and jumps to $(1,1)$ at
$\alpha=1$, as cohomology does at a special parameter value, with the alternating sum unchanged.

\section{A derivation and its defect; entropy modulo a prime}

The function $\partial(x)=-x\log x$ satisfies the Leibniz rule
\[ \partial(xy)=x\,\partial(y)+\partial(x)\,y, \]
but it is not additive, and entropy is its defect of additivity: for a distribution,
$H(p)=\sum_i\partial(p_i)-\partial\bigl(\sum_ip_i\bigr)$, the last term being $\partial(1)=0$. The chain rule is
then one line,
\[ \sum_{i,j}\partial(q_ip_{ij})=\sum_iq_i\sum_j\partial(p_{ij})+\sum_i\partial(q_i)\sum_jp_{ij}. \]
This way of seeing entropy does not need the real numbers. Let $p$ be a prime. On the integers the Fermat
quotient $\partial_p(a)=(a-a^p)/p$ satisfies $\partial_p(ab)\equiv a\,\partial_p(b)+\partial_p(a)\,b\pmod p$ and fails to
be additive.

\begin{definition}\label{def:modp}
Let $\pi\in\Fp^n$ with $\sum_i\pi_i=1$, and choose integers $a_i$ representing the $\pi_i$. The
\term{entropy of $\pi$ modulo $p$} is
\[ H_p(\pi)=\frac1p\Bigl(1-\sum_ia_i^p\Bigr)\bmod p\ \in\Fp. \]
\end{definition}

It is well defined because $a^p$ modulo $p^2$ depends only on $a$ modulo $p$.

\begin{theorem}\label{thm:modp}
\Sli[\cite{Kon95,Lei21p}] $H_p$ satisfies the chain rule
$H_p\bigl(\gamma\circ(\pi^1,\dots,\pi^n)\bigr)=H_p(\gamma)+\sum_i\gamma_iH_p(\pi^i)$, and every function on such
``distributions'' with values in $\Fp$ satisfying the chain rule is a multiple of it; no regularity
hypothesis is needed. For odd $p$,
\[ H_p(x,1-x)=\sum_{k=1}^{p-1}\frac{x^k}{k}, \]
a truncated logarithm, which satisfies \eqref{eq:FEITH} for all $x,y\in\Fp\setminus\{1\}$.
\end{theorem}

The polynomial was found by Kontsevich, who observed that it satisfies the fundamental equation; Leinster
identified the function it comes from and proved the uniqueness. The real and the mod $p$ theories are
parallel. Whether there is a single cohomological statement specializing to both is, as far as we know,
open (\cref{ch:coda}).

\section{The general setting, and higher degrees}

We have worked with all partitions of one finite set. Baudot and Bennequin, and in greater generality
Vigneaux, consider an \term{information structure}: a poset $\Sinf$ of observables in which the product of
two elements exists whenever they have a common refinement in $\Sinf$, with a functor of laws and a
presheaf of functions on it. For each $X$ the observables refined by $X$ form a monoid $\Sinf_X$; the
monoid algebras $\mathcal{A}_X=\R[\Sinf_X]$ form a presheaf of rings $\mathcal{A}$ on $\Sinf$; and the
functions form a presheaf of $\mathcal{A}$-modules.

\begin{theorem}\label{thm:topos}
\Sli[\cite{Vig20}] Information cohomology is $\Ext^\bullet_{\mathcal{A}}(\R,\Fun)$, computed in the abelian
category of $\mathcal{A}$-modules in the topos of presheaves on $\Sinf$. A relative bar resolution of the
trivial module $\R$ yields the complex of \cref{def:complex}. If every observable in $\Sinf$ can be written
as a product of two others in a nondegenerate way, $H^1$ is a product of copies of $\R$, one for each
connected component of $\Sinf$, each generated by a multiple of entropy.
\end{theorem}

The generality matters when not all observables are jointly measurable, as in quantum theory or in the
contextual situations studied by sheaf-theoretic methods. For our purposes the finite full structure is
enough.

About degrees above one much less is known. If the conditioning action is replaced by the trivial action,
the coboundary of entropy is $H[Y]+H[Z]-H[YZ]$, the mutual information, and the higher alternating sums are
the multivariate mutual informations \cite{BB15}; these fit together into Hu's theorem that entropy
extends to a signed measure on the Boolean algebra generated by the observables \cite{Hu62,Yeu08}. For the
conditioning action itself we know of no general computation of $H^n(\Omega)$ for $n\ge2$.

\section*{Notes}

Information cohomology was introduced by Baudot and Bennequin \cite{BB15}; the topos-theoretic foundations,
the bar resolution, and the treatment of the Tsallis case are due to Vigneaux \cite{Vig20,Vig19}, who also
treats Gaussian laws, where differential entropy and the dimension appear as cocycles. The fundamental
equation has a long history, for which see \cite{AD75}; its generalization of degree $\alpha$ is due to
Dar\'oczy \cite{Dar70}, and the entropies $S_\alpha$ to Havrda and Charv\'at \cite{HC67} and Tsallis
\cite{Tsa88}. Cathelineau \cite{Cat88} met the equation in the homology of $\mathrm{SL}_2$, which is the
origin of the connection with polylogarithms pursued in \cite{Kon95,EVG02}. Entropy modulo a prime is
developed by Leinster \cite{Lei21p}.

\section*{Exercises}

\begin{exercise}
Show that $Y._\alpha(Z._\alpha f)=(YZ)._\alpha f$ for every $\alpha>0$, and that the constant function $1$ is
invariant under the $\alpha$-action iff $\alpha=1$.
\end{exercise}

\begin{exercise}
Verify directly that $S_\alpha[YZ]=S_\alpha[Y]+Y._\alpha S_\alpha[Z]$. For independent $Y$ and $Z$ deduce
$S_\alpha[YZ]=S_\alpha[Y]+S_\alpha[Z]-(\alpha-1)S_\alpha[Y]S_\alpha[Z]$.
\end{exercise}

\begin{exercise}\label{exer:two}
Let $|\Omega|=2$. Describe all 1-cocycles and compute $H^1(\Omega)$.
\end{exercise}

\begin{exercise}
Show that $h(x)=x$ satisfies \eqref{eq:FEITH}, and that $\hb$ satisfies it by computing $H(x,y,1-x-y)$ in two
ways. Why does $h(x)=x$ not contradict \cref{thm:H1}?
\end{exercise}

\begin{exercise}
Prove the congruence $\partial_p(ab)\equiv a\,\partial_p(b)+\partial_p(a)\,b\pmod p$. Compute $H_5(2,4)$ from the
definition and from the truncated logarithm. Compute $H_3(2,2)$ and $H_3(1,1,2)$, and check the chain rule for
$(1,1,2)=(2,2)\circ\bigl((2,2),(1)\bigr)$ in $\mathbb{F}_3$.
\end{exercise}
%% ---- end ch/03-cocycle.tex ----
%% ---- begin ch/04-inequalities.tex ----
\chapter{Divergence and the Elementary Inequalities}\label{ch:inequalities}

Khinchin's second paper opens with a chapter of inequalities: two generalizations of Shannon's inequality
$H_A(B)\le H(B)$ and three lemmas taken from Feinstein. They are the working tools of the later chapters.
All of them follow from one fact, the positivity of relative entropy, together with the chain rule; and the
form in which they are used, the data-processing inequality, says that composition of Markov kernels is
non-expansive for a divergence. That statement is an enrichment of the category $\FinStoch$, and this
chapter is organized around it.

\section{Relative entropy}

\begin{definition}
For distributions $p,q$ on a finite set $X$, the \term{relative entropy}, or Kullback--Leibler divergence,
is
\[ \KL pq=\sum_xp(x)\log\frac{p(x)}{q(x)}, \]
with the conventions $0\log\frac0q=0$ and $\KL pq=\infty$ if $p(x)>0=q(x)$ for some $x$.
\end{definition}

\begin{proposition}[Gibbs' inequality]\label{prop:gibbs}
\Scl $\KL pq\ge0$, with equality iff $p=q$.
\end{proposition}

\begin{proof}
$\ln t\le t-1$ with equality only at $t=1$, so $-\sum_xp(x)\ln\frac{q(x)}{p(x)}\ge\sum_x(p(x)-q(x))\ge0$, the sums being
over the support of $p$.
\end{proof}

For a state $p$ on $X$ and a kernel $f\colon X\to Y$ write $p\rtimes f$ for the joint distribution
$p(x)f(y\st x)$ on $X\times Y$.

\begin{proposition}[Chain rule for relative entropy]\label{prop:chainD}
\Scl For joint distributions $r,r'$ on $X\times Y$ with first marginals $p,p'$,
\[ \KL r{r'}=\KL p{p'}+\sum_xp(x)\,\KL{r(\,\cdot\st x)}{r'(\,\cdot\st x)}. \]
\end{proposition}

\begin{theorem}[Data processing]\label{thm:DPI}
\Scl For every kernel $f\colon X\to Y$ and states $p,p'$ on $X$,
\[ \KL{f\circ p}{f\circ p'}\le\KL p{p'}. \]
\end{theorem}

\begin{proof}
Apply \cref{prop:chainD} to $r=p\rtimes f$ and $r'=p'\rtimes f$ in two ways. Conditioning on $X$, the conditional
distributions agree, so $\KL r{r'}=\KL p{p'}$. Conditioning on $Y$,
$\KL r{r'}=\KL{f\circ p}{f\circ p'}+\sum_y(f\circ p)(y)\,\KL{r(\,\cdot\st y)}{r'(\,\cdot\st y)}$, and the last sum is nonnegative by
\cref{prop:gibbs}.
\end{proof}

The proof shows what the inequality is made of. The chain rule is an identity, and we saw in
\cref{ch:schemes} that for entropy it is functoriality. Positivity is an order relation. Data processing is
the two together.

\section{Composition is short}

Relative entropy between states extends to parallel morphisms. For $f,g\colon X\to Y$ in $\FinStoch$ put
\[ \KL fg=\max_{x\in X}\KL{f(\,\cdot\st x)}{g(\,\cdot\st x)}. \]

\begin{theorem}\label{thm:enriched}
\Sli[\cite{Per24}] With this divergence on its hom-sets, $\FinStoch$ is a Markov category enriched in
divergence spaces: for all composable morphisms,
\begin{gather*}
 \KL{h\circ f}{h\circ g}\le\KL fg,\qquad\KL{f\circ k}{g\circ k}\le\KL fg,\\
 \KL{f\otimes f'}{g\otimes g'}=\KL fg+\KL{f'}{g'}.
\end{gather*}
\end{theorem}

\begin{proof}
The first inequality is \cref{thm:DPI} applied to each input. The second follows from the joint convexity of
relative entropy, since $(f\circ k)(\,\cdot\st w)$ is a mixture of the $f(\,\cdot\st x)$ with weights
$k(x\st w)$. The third is additivity of relative entropy on product distributions.
\end{proof}

A \term{divergence space} is a set with a function $D$ to $[0,\infty]$ vanishing on the diagonal; no symmetry
or triangle inequality is asked. The theorem says that composition and tensoring are non-expansive maps of
such spaces. The same holds for other divergences, for instance the R\'enyi divergences and the total
variation distance $\TV(p,q)=\frac12\sum_x|p(x)-q(x)|$, which is a metric. This is the pattern announced at the
end of \cref{ch:schemes}: an equation for deterministic morphisms, here $f\circ p=f\circ p'$ following
from $p=p'$, has a quantitative form for all morphisms.

\section{Entropy as distance from determinism}

A state $p$ on $X$ is deterministic when $\cpy_X\circ p=p\otimes p$: drawing once and copying is the same as
drawing twice. For a general state the two sides differ, and the difference can be measured.

\begin{proposition}\label{prop:copy}
\Sli[\cite{Per24}] For a state $p$ on $X$ and a joint state $r$ on $X\times Y$ with marginals $p,q$,
\[ H(p)=\KL{\cpy_X\circ p}{p\otimes p},\qquad I(X;Y)=\KL r{p\otimes q}. \]
With total variation in place of relative entropy the first expression becomes $1-\sum_xp(x)^2$.
\end{proposition}

\begin{proof}
$\cpy_X\circ p$ is concentrated on the diagonal with weights $p(x)$, and
$\sum_xp(x)\log\frac{p(x)}{p(x)^2}=H(p)$. The second formula is $\sum r\log r-\sum r\log p-\sum r\log q$. For the last
statement, $\frac12\bigl[\sum_x(p(x)-p(x)^2)+\sum_{x\ne x'}p(x)p(x')\bigr]=1-\sum_xp(x)^2$.
\end{proof}

So entropy is the mutual information of a variable with itself, and it is defined by the Markov category
structure together with the divergence. The quantity $1-\sum_xp(x)^2$ is the Gini--Simpson index of
ecology. Entropy and mutual information need no separate axiomatization once the enrichment is given; what
needs a choice is the divergence.

\section{Shannon's inequality and its two generalizations}

By \cref{prop:copy,prop:gibbs}, $I(X;Y)\ge0$, which is Shannon's inequality $H_A(B)\le H(B)$.

Khinchin's first generalization is contained in the proof we gave of \cref{prop:properties}(iv). That proof
applied Jensen's inequality for each value of the second variable separately, and therefore proves more
than the summed statement.

\begin{lemma}[Khinchin's Lemma 1.1]\label{lem:partial}
\Scl[\cite{Khi56}] Let $r$ be a joint distribution on $X\times Y$ with marginals $p,q$. For every subset
$S\subseteq Y$,
\[ -\sum_xp(x)\sum_{y\in S}r(y\st x)\log r(y\st x)\ \le\ -\sum_{y\in S}q(y)\log q(y). \]
\end{lemma}

The second generalization is the conditional form.

\begin{lemma}[Khinchin's Lemma 1.2]\label{lem:SSA}
\Scl[\cite{Khi56}] For three schemes, $H_{AB}(C)\le H_B(C)$. Equivalently, the \term{conditional mutual
information} $I(A;C\st B)=H_B(C)-H_{AB}(C)$ is nonnegative.
\end{lemma}

\begin{proof}
$I(A;C\st B)=\sum_bP(b)\,I(A;C)_{P|_b}$, an average of mutual informations.
\end{proof}

In the language of \cref{ch:cocycle} these inequalities are statements about the function $X\mapsto H[X](P)$
on the monoid of observables, for a fixed law $P$. Recall that $XY$ is the join of $X$ and $Y$ in the
refinement order; write $X\wedge Y$ for the meet, the finest observable refined by both.

\begin{proposition}\label{prop:submodular}
\Scl[cf.\ \cite{Fuj78}] For every law $P$ the function $H[\,\cdot\,](P)$ on $\Pi(\Omega)$ is
\begin{enumerate}[label=(\roman*)]
\item monotone: $H[X]\ge H[Y]$ if $X$ refines $Y$;
\item submodular: $H[XY]+H[X\wedge Y]\le H[X]+H[Y]$;
\item and satisfies $H[XYZ]+H[Y]\le H[XY]+H[YZ]$ for all $X,Y,Z$.
\end{enumerate}
\end{proposition}

\begin{proof}
(i) is \cref{thm:functor}. (iii) is \cref{lem:SSA}, since $H_{XY}(Z)=H[XYZ]-H[XY]$. For (ii), $X\wedge Y$ is a
function of $X$ and of $Y$, so with $W=X\wedge Y$ we have $H[XW]=H[X]$ and $H[WY]=H[Y]$, and (iii) for
$X,W,Y$ reads $H[XY]+H[W]\le H[X]+H[Y]$.
\end{proof}

The difference between the two sides of (ii) is $I(X;Y)-H[X\wedge Y]$. The meet is the part of the
information that $X$ and $Y$ share as an observable; the mutual information can be much larger, and is
positive for two correlated bits whose meet is trivial (\cref{exer:meet}).

\section{Feinstein's three inequalities}

The remaining lemmas of Khinchin's first chapter concern decoding. Let $r$ be a joint distribution on
$X\times Y$ with marginals $p,q$; think of $x$ as sent and $y$ as received. The \term{maximum a posteriori}
rule decodes $y$ as an $x$ maximizing $r(x,y)$, and its probability of error is
\[ P_e=1-\sum_y\max_xr(x,y). \]

\begin{lemma}[Khinchin's Lemmas 2.1--2.3]\label{lem:feinstein3}
\Scl[\cite{Fei54,Khi56}]
\begin{enumerate}[label=(\roman*)]
\item Let $Z\subseteq X\times Y$ with $r(Z)>1-\delta_1$ and $U_0\subseteq X$ with $p(U_0)>1-\delta_2$. For
$\alpha>0$ let $U_1$ be the set of $x\in U_0$ with $r(\{y:(x,y)\notin Z\}\st x)\le\alpha$. Then
$p(U_1)>1-\delta_2-\delta_1/\alpha$.
\item If there are pairwise disjoint sets $\Delta_x\subseteq Y$ with $r(\Delta_x\st x)>1-\varepsilon$ for
every $x$, then $P_e<\varepsilon$.
\item (Fano's inequality.) If $|X|=n>1$, then $H(X\st Y)\le\hb(P_e)+P_e\log(n-1)$.
\end{enumerate}
\end{lemma}

\begin{proof}
(i) $\sum_xp(x)\,r(\{y:(x,y)\notin Z\}\st x)=1-r(Z)<\delta_1$, so by Markov's inequality the set of $x$ where
the conditional probability exceeds $\alpha$ has $p$-measure less than $\delta_1/\alpha$. (ii) The rule
that decodes $y\in\Delta_x$ as $x$ is correct with probability $\sum_xp(x)\,r(\Delta_x\st x)>1-\varepsilon$, and no
rule does better than the maximum a posteriori rule, because $\sum_yr(d(y),y)\le\sum_y\max_xr(x,y)$ for every map
$d$. (iii) Given $y$, the posterior $r(\,\cdot\st y)$ has largest entry $1-e_y$, where $e_y$ is the conditional
probability of error. By \cref{exer:grouping}, $H(r(\,\cdot\st y))\le\hb(e_y)+e_y\log(n-1)$. Average
over $y$ and use the concavity of $\hb$.
\end{proof}

Part (ii) says that a decoder is a map $d\colon Y\to X$ and that among all maps the pointwise maximizer of
the Bayesian inverse is best. Part (iii) is the quantitative form of a triviality. If a kernel
$f\colon X\to Y$ has a deterministic left inverse, $d\circ f=\id_X$, then $x$ is a function of $y$ and
$H(X\st Y)=0$. Fano's inequality says that if $d\circ f$ is within $\varepsilon$ of the identity, in the
sense that $d(y)\ne x$ with probability at most $\varepsilon$, then the equivocation is at most
$\hb(\varepsilon)+\varepsilon\log(n-1)$. Approximate retractions lose approximately nothing.
\Cref{ch:feinstein} is built on this notion.

\section{Relative entropy as a functor}

Entropy is a functor on $\FinProb$ (\cref{thm:functor}) and is characterized by that
(\cref{thm:BFL}). Relative entropy has the same status on a slightly larger category. Let $\FinStat$ have
finite probability spaces as objects; a morphism $(X,p)\to(Y,q)$ is a pair $(f,s)$ of a
measure-preserving map $f\colon X\to Y$ and a kernel $s\colon Y\to X$ with $f\circ s=\id_Y$, thought of as a
hypothesis about how $x$ is distributed given $f(x)$. Composition is $(g,t)\circ(f,s)=(g\circ f,s\circ t)$.

\begin{theorem}[Baez--Fritz]\label{thm:BF}
\Sli[\cite{BF14}] The assignment $(f,s)\mapsto\KL p{s\circ q}$ is a functor $\FinStat\to[0,\infty]$. It is lower
semicontinuous and convex-linear, and it vanishes when $s$ is the Bayesian inverse of $f$. Every functor
with these properties is a constant multiple of it.
\end{theorem}

Functoriality here is \cref{prop:chainD}. The quantity $\KL p{s\circ q}$ is the information gained on learning
that the true distribution is $p$, when one's prior was built from the correct marginal $q$ and the
hypothesis $s$.

\section{Beyond the elementary inequalities}

Every inequality proved so far is a consequence of \cref{prop:submodular}, that is, of monotonicity and
submodularity. Such consequences are called Shannon-type. They are all there is for up to three variables.

\begin{theorem}\label{thm:nonshannon}
\Scl[\cite{ZY98,Mat07}] For four or more random variables there are linear inequalities among their joint
entropies that hold for all distributions and are not consequences of monotonicity and submodularity;
there are infinitely many independent ones, and the closure of the set of entropy vectors is a convex
cone that is not polyhedral.
\end{theorem}

Khinchin's elementary inequalities are thus the first layer of a structure that is not finitely describable.
Neither the cohomological account of \cref{ch:cocycle} nor the enriched one of this chapter explains the
further layers. We record this as a limit of what is understood, not of what was needed: the coding
theorems use only the first layer.

\section*{Notes}

Relative entropy is due to Kullback and Leibler; for the classical theory see \cite{CT06,CK11}. The
enriched-category view of data processing and \cref{prop:copy} are due to Perrone \cite{Per24}. The
generalized Shannon inequalities and Feinstein's lemmas are \cite[Ch.~I]{Khi56}, after \cite{Fei54}; Fano's
inequality is in \cite{Fan61}. Submodularity of entropy and the polymatroid point of view go back to
Fujishige \cite{Fuj78}; non-Shannon inequalities were discovered by Zhang and Yeung \cite{ZY98}, and the
non-polyhedrality is due to Mat\'u\v{s} \cite{Mat07}. See \cite{Yeu08} for the whole subject. The category
$\FinStat$ and \cref{thm:BF} are from \cite{BF14}.

\section*{Exercises}

\begin{exercise}
For $p=(\tfrac12,\tfrac12)$ and $q=(\tfrac14,\tfrac34)$ compute $\KL pq$ and $\KL qp$. Let $f$ be the binary
symmetric channel that flips its input with probability $0.1$. Compute $\KL{f\circ p}{f\circ q}$ and compare.
\end{exercise}

\begin{exercise}
Prove \cref{prop:chainD}, and show that equality holds in \cref{thm:DPI} iff the two Bayesian inverses agree:
$r(\,\cdot\st y)=r'(\,\cdot\st y)$ for all $y$ in the support of $f\circ p$.
\end{exercise}

\begin{exercise}
Compute $\TV(\cpy\circ p,\,p\otimes p)$ and $\KL{\cpy\circ p}{p\otimes p}$ for $p=(\tfrac12,\tfrac14,\tfrac14)$.
For which states on $n$ points is each largest?
\end{exercise}

\begin{exercise}\label{exer:meet}
Let $X,Y$ be bits with joint distribution $r(0,0)=r(1,1)=0.4$, $r(0,1)=r(1,0)=0.1$. Compute $I(X;Y)$ and show
that $X\wedge Y$ is trivial. Then give an example in which $I(X;Y)=H[X\wedge Y]>0$.
\end{exercise}

\begin{exercise}
Let $X$ be uniform on $n$ points and let $Y=X$ with probability $1-\varepsilon$, and otherwise uniform on the
other $n-1$ points, with $\varepsilon<1-\tfrac1n$. Show that equality holds in Fano's inequality.
\end{exercise}
%% ---- end ch/04-inequalities.tex ----
\part{Sources}
%% ---- begin ch/05-sources.tex ----
\chapter{Sources}\label{ch:sources}

A source, for Khinchin, is a probability measure $\mu$ on the space $\AZ$ of doubly infinite sequences of
letters from a finite alphabet $A$; it is stationary when $\mu$ is invariant under the shift. This chapter
sets up the same objects in a Markov category. The sequence space is an infinite tensor product, a source is
a state on it, and stationary sources and the maps between them are the states and morphisms of a category
of dynamical systems. We then define the entropy rate, compute it for Markov chains as Khinchin does in his
first paper, and read finite-state sources as coalgebras.

\section{Sequence spaces}

Let $\BorelStoch$ be the category of standard Borel spaces and Markov kernels; it is a Markov category
containing $\FinStoch$, and its deterministic morphisms are the measurable maps (\cref{app:toolkit}). For a
finite alphabet $A$ the space $\AZ$ carries the product $\sigma$-algebra $\FF_A$, generated by the
\term{cylinders}, the sets of sequences with prescribed letters at finitely many places. For a finite set
$F\subset\Z$ let $\pi_F\colon\AZ\to A^F$ be the projection.

\begin{theorem}[Kolmogorov extension]\label{thm:kolmogorov}
\Sli[\cite{FR20}] In $\BorelStoch$ the object $\AZ$, with the projections $\pi_F$, is the limit of the diagram
of finite powers $A^F$ and marginalization maps, and this limit is preserved by tensoring with any object.
Explicitly, for every $Y$ the kernels $Y\to\AZ$ correspond bijectively to families of kernels
$k_F\colon Y\to A^F$ that are compatible with marginalization.
\end{theorem}

Such a limit is called a \term{Kolmogorov product}, and $\AZ=\bigotimes_{n\in\Z}A$ is the infinite tensor
power of $A$. For $Y=1$ the theorem is the classical statement that a measure on $\AZ$ is the same as a
consistent family of finite-dimensional distributions. The Kolmogorov product is a categorical product only
in the subcategory of deterministic morphisms. A kernel into $\AZ$ is not determined by its components into
the single factors $A$, and this failure will matter below.

\section{Stationary sources}

The \term{shift} $T\colon\AZ\to\AZ$, $(Tx)_n=x_{n+1}$, is a deterministic isomorphism. A \term{source} $[A,\mu]$
is a state $\mu\colon1\to\AZ$; it is \term{stationary} if $T\circ\mu=\mu$. By \cref{thm:kolmogorov} a stationary
source is the same as a sequence of distributions $\mu_n$ on $A^n$, $n\ge1$, the laws of the blocks
$x_1\dots x_n$, such that both the first $n$ and the last $n$ letters of a block distributed by $\mu_{n+1}$
are distributed by $\mu_n$.

\begin{definition}\label{def:dyn}
$\Dyn$ is the category whose objects are pairs $(X,T_X)$ of a standard Borel space and a measurable
automorphism, and whose morphisms $(X,T_X)\to(Y,T_Y)$ are the Markov kernels $k\colon X\to Y$ that are
\term{equivariant}: $k\circ T_X=T_Y\circ k$.
\end{definition}

\begin{proposition}\label{prop:dyn}
\Sli[\cite{Fri20}, \S7] $\Dyn$ is a Markov category, with tensor product, copy and delete maps inherited from
$\BorelStoch$. Its unit object is the one-point system, and:
\begin{enumerate}[label=(\roman*)]
\item a state $1\to(\AZ,T)$ is a stationary source;
\item a deterministic morphism $(\AZ,T)\to(\BZ,T)$ is a measurable map commuting with the shifts, a
\term{stationary code};
\item a general morphism $(\AZ,T)\to(\BZ,T)$ is a stationary channel in the sense of \cref{ch:channels}.
\end{enumerate}
\end{proposition}

The only point to check is that the copy maps are equivariant, and they are because $T$ is deterministic.
The proposition puts Khinchin's three kinds of object in one place. His remark that a code may be regarded
as a channel is the inclusion of the deterministic morphisms among all morphisms.

\section{The entropy rate}

For a stationary source $\mu$ write $H_n=H(\mu_n)$ for the entropy of a block of length $n$, and $H_0=0$.

\begin{proposition}\label{prop:rate}
\Scl[\cite{Sha48,Khi56}] Let $\mu$ be stationary.
\begin{enumerate}[label=(\roman*)]
\item $H_{m+n}\le H_m+H_n$.
\item The increments $c_n=H_{n+1}-H_n=H(x_0\st x_{-n},\dots,x_{-1})$ are nonincreasing in $n$.
\item The limits $\lim_nH_n/n$ and $\lim_nc_n$ exist and are equal, and equal $\inf_nH_n/n$.
\end{enumerate}
\end{proposition}

\begin{proof}
(i) is Shannon's inequality for the two halves of a block, whose laws are $\mu_m$ and $\mu_n$ by
stationarity. (ii) is \cref{lem:SSA}: conditioning on one more letter of the past does not increase the
entropy; stationarity identifies the conditional entropies with the increments. (iii) $H_n=\sum_{k<n}c_k$ is
a sum of a nonincreasing nonnegative sequence, so $H_n/n$ converges to $\lim c_k$; the infimum is Fekete's
lemma for the subadditive sequence $H_n$.
\end{proof}

\begin{definition}
The common value $H(\mu)$ of the limits in \cref{prop:rate} is the \term{entropy} of the source, in bits per
letter. It satisfies $0\le H(\mu)\le\log|A|$.
\end{definition}

For the source that emits independent letters with distribution $p$, the state $p^{\otimes\Z}$, the block
entropies are $H_n=nH(p)$ and the entropy of the source is $H(p)$. The second expression in (iii) has a
meaning that the first hides: $H(\mu)$ is the uncertainty of the next letter given the entire past. We make
this precise in \cref{ch:martingales}.

\section{Stationary codes and cofreeness}

A stationary code $\phi\colon\AZ\to\BZ$ is determined by its coordinate at time zero,
$\phi_0=\pi_0\circ\phi\colon\AZ\to B$, since $\phi(x)_n=\phi_0(T^nx)$. This is a universal property.

\begin{proposition}\label{prop:cofree}
\Srf[\cite{Hed69}] In the category of sets, of measurable spaces, or of compact Hausdorff spaces, let $(X,T_X)$ be
an object with an automorphism. Then composition with $\pi_0$ is a bijection between equivariant maps
$(X,T_X)\to(\BZ,T)$ and maps $X\to B$. That is, $(\BZ,T)$ is the cofree system on $B$. Consequently:
\begin{enumerate}[label=(\roman*)]
\item stationary codes $\AZ\to\BZ$ correspond to measurable functions $\AZ\to B$;
\item continuous equivariant maps $\AZ\to\BZ$ correspond to continuous functions $\AZ\to B$, which by
compactness depend on finitely many coordinates: they are the \term{sliding block codes}
$\phi(x)_n=\Phi(x_{n-r},\dots,x_{n+r})$ (the Curtis--Hedlund--Lyndon theorem).
\end{enumerate}
In $\BorelStoch$ the corresponding statement is false.
\end{proposition}

\begin{proof}
Given $g\colon X\to B$ define $\phi(x)_n=g(T_X^nx)$. This is the unique equivariant map with $\pi_0\circ\phi=g$,
and it is measurable or continuous when $g$ is, because $\BZ$ is the product in those categories. A
continuous function from the compact space $\AZ$ to the finite discrete space $B$ is locally constant, and
finitely many cylinders on which it is constant cover $\AZ$. For the last statement let $X=1$: an
equivariant kernel $1\to\BZ$ is a stationary source, a kernel $1\to B$ is a distribution on $B$, and many
stationary sources have the same one-letter marginal.
\end{proof}

The failure in the stochastic case is not a technicality. An equivariant kernel $\nu\colon\AZ\to\BZ$
consists of its time-zero marginal $\AZ\to B$ and, in addition, of the dependence among the output letters
for a fixed input. The first part is what Khinchin's notion of the memory of a channel controls. The
second is not controlled by it, and we shall see in \cref{ch:channels} that this is exactly where his
treatment of ergodicity has a gap.

\section{Markov chains}

Let $Q=(q_{ab})$ be a stochastic matrix on $A$ and $\pi$ a stationary distribution, $\pi Q=\pi$. The
\term{stationary Markov source} has block laws $\mu_n(x_1\dots x_n)=\pi(x_1)\,q_{x_1x_2}\cdots q_{x_{n-1}x_n}$.

\begin{proposition}\label{prop:markov}
\Scl[\cite{Sha48}; \cite{Khi53}, \S3] The entropy of the stationary Markov source is
\[ H(\mu)=\sum_a\pi(a)\,H(q_{a\,\cdot})=-\sum_{a,b}\pi(a)\,q_{ab}\log q_{ab}. \]
\end{proposition}

\begin{proof}
By the Markov property $c_n=H(x_0\st x_{-1})$ for all $n\ge1$.
\end{proof}

\begin{example}\label{ex:markov}
Let $A=\{0,1\}$ with $q_{01}=0.1$ and $q_{10}=0.3$. Then $\pi=(0.75,0.25)$ and
$H(\mu)=0.75\,\hb(0.1)+0.25\,\hb(0.3)\approx0.572$ bits per letter. A source emitting independent letters with the
same marginal has entropy $\hb(0.25)\approx0.811$. The difference is what the memory of the chain is worth to
someone predicting it.
\end{example}

\section{Finite-state sources as coalgebras}

A Markov chain is the simplest machine that emits a sequence. The general finite machine has a finite set
$S$ of internal states and, at each step, emits a letter and moves to a new state, the pair being drawn
from a distribution that depends on the current state. That is a morphism
\[ c\colon S\longrightarrow A\times S\quad\text{in }\FinStoch, \]
a coalgebra for the functor $A\times-$. With an initial distribution on $S$ it generates a process, called
a hidden Markov source or a function of a Markov chain.

\begin{theorem}\label{thm:trace}
\Sli[\cite{KK13}; cf.\ \cite{HJS07}] In $\BorelStoch$ the space $A^{\N}$ of one-sided sequences, with the
isomorphism $A^{\N}\iso A\times A^{\N}$ splitting off the first letter, is the final coalgebra of the functor
$A\times-$. For a coalgebra $c\colon S\to A\times S$ the unique coalgebra morphism $S\to A^{\N}$ assigns to
each state the law of the sequence emitted from it.
\end{theorem}

Uniqueness is the extension theorem again: a coalgebra morphism is determined on cylinders by induction on
their length. If the initial distribution $\sigma$ is invariant for the state process, the emitted
one-sided process is stationary and extends uniquely to a stationary source on $\AZ$.

The entropy of such a source is not given by a formula in terms of $c$ and $\sigma$ in general, but there
is a case where it is. Call $c$ \term{unifilar} if the next state is a function of the current state and
the emitted letter, $c(a,s'\st s)=e_s(a)\,[s'=\tau(s,a)]$.

\begin{proposition}\label{prop:unifilar}
\Scl[\cite{Sha48}] For a unifilar coalgebra with invariant state distribution $\sigma$,
$H(\mu)=\sum_s\sigma(s)\,H(e_s)$.
\end{proposition}

\begin{proof}
Let $s_0$ be the initial state. Given $s_0$ and $x_0,\dots,x_{n-1}$ the state $s_n$ is determined, so
$H(x_n\st x_0,\dots,x_{n-1},s_0)=\sum_s\sigma(s)H(e_s)$ for every $n$. Hence $H_n\ge H(x_0\dots x_{n-1}\st s_0)=n\sum_s\sigma(s)H(e_s)$ and
$H_n\le H(s_0)+H(x_0\dots x_{n-1}\st s_0)$. Divide by $n$.
\end{proof}

A general coalgebra can be made unifilar at the cost of enlarging the state space. Replace the state by the
\term{belief}, the conditional distribution $b\in\Delta(S)$ of the current state given the letters emitted
so far. The belief emits a letter with distribution $e_b=\sum_sb(s)\,c(\,\cdot\,,S\st s)$ and is then updated
by Bayes' rule to a new belief $\tau(b,a)$ that is a function of $b$ and the letter. This is the
determinization of the coalgebra in the sense of the generalized powerset construction \cite{SBBR13},
carried out for the distribution monad instead of the powerset.

\begin{theorem}[Blackwell]\label{thm:blackwell}
\Srf[\cite{Bla57}] Let $\beta$ be a stationary distribution of the belief process on $\Delta(S)$ arising from
the invariant initial distribution $\sigma$. Then
\[ H(\mu)=\int_{\Delta(S)}H(e_b)\,d\beta(b), \]
which is the formula of \cref{prop:unifilar} for the determinized coalgebra. For every $n\ge1$,
\[ H(x_n\st x_0,\dots,x_{n-1},s_0)\ \le\ H(\mu)\ \le\ H(x_n\st x_0,\dots,x_{n-1}), \]
and both bounds converge to $H(\mu)$.
\end{theorem}

The measure $\beta$ can be singular and is not computable in closed form in general; that is the sense in
which the entropy of a hidden Markov source has no formula. The bounds are effective.

\begin{example}\label{ex:hmm}
Let the state follow the chain of \cref{ex:markov} and let the emitted letter be the state passed through a
binary symmetric channel with flip probability $0.2$. The lower and upper bounds of \cref{thm:blackwell} are
$0.9033$ and $0.9055$ at $n=4$ and agree to four places, at $0.9052$, from $n=8$ on. Hiding the state behind
noise has raised the entropy from $0.572$ to $0.905$ bits per letter.
\end{example}

\section{Entropy as an invariant}

Let $\phi\colon(\AZ,\mu)\to(\BZ,\eta)$ be a stationary code with $\phi\circ\mu=\eta$; one says that $\eta$ is a
\term{factor} of $\mu$.

\begin{theorem}[Kolmogorov--Sinai]\label{thm:KS}
\Scl[\cite{Kol58,Sin59}] If $\eta$ is a factor of $\mu$ then $H(\eta)\le H(\mu)$. In particular isomorphic
stationary sources have the same entropy.
\end{theorem}

\begin{proof}[Proof for sliding block codes]
If $\phi$ has window radius $r$, a block of $n$ output letters is a function of a block of $n+2r$ input
letters, so $H_n(\eta)\le H_{n+2r}(\mu)$ by \cref{thm:functor}. Divide by $n$. The general case follows by
approximating a measurable $\phi_0$ by functions of finitely many coordinates.
\end{proof}

So the entropy rate is a functor from stationary sources and stationary codes to the poset
$([0,\infty),\ge)$. It is the infinite-time counterpart of \cref{thm:functor}, with one difference: for
finite schemes the functor recorded the amount lost, a number attached to each morphism, and here only
the inequality survives. It does not extend to a monotone function along stochastic morphisms. A noisy
channel can raise the entropy of what passes through it, as \cref{ex:hmm} shows. The quantity that behaves
well for all morphisms of $\Dyn$ is the information rate of \cref{ch:channels}.

Kolmogorov introduced \cref{thm:KS} into ergodic theory in 1958, taking the definition from Shannon, in
order to show that the independent sources with distributions $(\tfrac12,\tfrac12)$ and
$(\tfrac13,\tfrac13,\tfrac13)$ are not isomorphic. Khinchin's papers, which appeared in the years just before,
were among the routes by which Shannon's ideas reached Soviet probabilists.

\section*{Notes}

The categorical treatment of infinite products is due to Fritz and Rischel \cite{FR20}; categories of
diagrams in a Markov category are in \cite[\S7]{Fri20}. For the classical theory of sources see
\cite{Gra11,Bil65}. The Curtis--Hedlund--Lyndon theorem is \cite{Hed69}; see \cite{LM95}. Coalgebraic trace
semantics for probabilistic systems was developed in \cite{HJS07,KK13}, and determinization in \cite{SBBR13}.
Blackwell's theorem is \cite{Bla57}; the bounds are in \cite[\S4.5]{CT06}.

\section*{Exercises}

\begin{exercise}
For the Markov source with $q_{01}=a$ and $q_{10}=b$, show that $H(\mu)=\frac{b\,\hb(a)+a\,\hb(b)}{a+b}$, and find the
maximum over $a,b$. When is $H(\mu)$ equal to the entropy of the one-letter marginal?
\end{exercise}

\begin{exercise}
Let $\mu$ be a stationary source on $\{0,1\}$ and let $\phi$ be the sliding block code
$\phi(x)_n=x_n+x_{n+1}\bmod2$. Show that $H(\phi\circ\mu)\le H(\mu)$ directly, and that equality holds when
$\mu$ is the source of independent fair bits. Is $\phi$ an isomorphism in that case?
\end{exercise}

\begin{exercise}\label{exer:cofreefinite}
Let $N\ge1$ and let $\Z/N$ act on $B^{\Z/N}$ by rotation. Show that for every $\Z/N$-set $X$, equivariant maps
$X\to B^{\Z/N}$ correspond to maps $X\to B$, and count the equivariant maps $A^{\Z/N}\to B^{\Z/N}$.
\end{exercise}

\begin{exercise}
Let $c\colon S\to A\times S$ be a coalgebra in which the next state is a function $s'=\tau(a)$ of the emitted
letter alone. Show that it generates a Markov source on $A$, find the transition matrix, and compute the
entropy. Show that every stationary Markov source arises in this way with $S=A$.
\end{exercise}

\begin{exercise}
Prove the upper and lower bounds of \cref{thm:blackwell}, and show that the lower bound is nondecreasing and
the upper bound nonincreasing in $n$.
\end{exercise}
%% ---- end ch/05-sources.tex ----
%% ---- begin ch/06-ergodic.tex ----
\chapter{Ergodic Sources}\label{ch:ergodic}

The coding theorems are about what happens along a single long sequence, and a statement about one
sequence can reflect the source only if the source does not secretly consist of several. Ergodicity is the
hypothesis that it does not. This chapter states it in three equivalent ways: by invariant sets, as
Khinchin does; as extremality in the convex set of stationary sources; and as determinism on the invariant
$\sigma$-algebra, in the formulation of Moss and Perrone. It then shows that the entropy of a source is an
affine function, which is why the ergodic case is the only one that needs to be treated.

\section{Invariant sets}

Let $[A,\mu]$ be a stationary source. A set $S\in\FF_A$ is \term{invariant} if $T^{-1}S=S$. The invariant sets
form a $\sigma$-algebra $\II$. A measurable function is $\II$-measurable iff it is invariant,
$f\circ T=f$.

\begin{definition}
A stationary source is \term{ergodic} if every invariant set has measure $0$ or $1$; equivalently, if every
invariant function is almost surely constant.
\end{definition}

\begin{proposition}\label{prop:iid}
\Scl The source $p^{\otimes\Z}$ of independent letters is ergodic. A stationary Markov source with irreducible
transition matrix is ergodic.
\end{proposition}

\begin{proof}
Let $S$ be invariant and $\varepsilon>0$. Choose a set $C$ depending on the coordinates in $[-m,m]$ with
$\mu(S\triangle C)<\varepsilon$. For $n>2m$ the set $T^{-n}C$ depends on a disjoint window, so for independent
letters $\mu(C\cap T^{-n}C)=\mu(C)^2$. Since $S=S\cap T^{-n}S$, we get $|\mu(S)-\mu(S)^2|<4\varepsilon$, and
$\mu(S)\in\{0,1\}$. For a Markov source the same argument works with $\mu(C\cap T^{-n}C)$ replaced by its
Ces\`aro averages, which converge to $\mu(C)^2$ when the matrix is irreducible.
\end{proof}

A mixture $\lambda\mu'+(1-\lambda)\mu''$ of two different stationary sources, $0<\lambda<1$, is stationary and
never ergodic (\cref{cor:extreme}).

\begin{theorem}[Birkhoff]\label{thm:birkhoff}
\Scl[\cite{Bir31}] Let $\mu$ be stationary and $f\in L^1(\mu)$. The averages
$A_nf=\frac1n\sum_{k=0}^{n-1}f\circ T^k$ converge almost surely and in $L^1$ to the conditional expectation
$\E[f\st\II]$. If $\mu$ is ergodic the limit is the constant $\int f\,d\mu$.
\end{theorem}

Khinchin quotes this theorem and uses the almost sure statement. For McMillan's theorem in the form he
proves, convergence in $L^1$ is enough, and that part has a short proof by Hilbert space geometry which we
give in \cref{ch:martingales}.

\section{The simplex of stationary sources}

Let $M_T(A)$ be the set of stationary sources with alphabet $A$, with the topology of convergence of the
probabilities of cylinders.

\begin{theorem}[Ergodic decomposition]\label{thm:decomposition}
\Scl $M_T(A)$ is a compact convex metrizable set, and a Choquet simplex. Its extreme points are the ergodic
sources. Every stationary $\mu$ has a unique representation
\[ \mu=\int\mu_e\,d\lambda(e) \]
with $\lambda$ a probability measure on the ergodic sources. Concretely, the regular conditional
probability $\mu_x$ of $\mu$ given $\II$ is an ergodic source for almost every $x$, and
$\mu=\int\mu_x\,d\mu(x)$.
\end{theorem}

\begin{corollary}\label{cor:extreme}
\Scl Two different ergodic sources are mutually singular, and a proper mixture of two different stationary
sources is not ergodic.
\end{corollary}

\begin{proof}
If $\mu\ne\mu'$ are ergodic there is a cylinder $C$ with $\mu(C)\ne\mu'(C)$. By \cref{thm:birkhoff} the
invariant set on which the frequency of visits to $C$ converges to $\mu(C)$ has $\mu$-measure $1$ and
$\mu'$-measure $0$. Under a proper mixture it has measure strictly between $0$ and $1$.
\end{proof}

\section{Ergodicity as determinism}

The classical definition speaks of sets of measure zero or one. In a Markov category there is a name for a
state that assigns every event probability zero or one: it is a deterministic state. The catch is that an
ergodic source is certainly not deterministic as a state on $\AZ$. It is deterministic on a quotient.

Work in the Markov category $\Stoch$ of all measurable spaces and Markov kernels. Let $G$ be a group or
monoid acting on an object $X$ by deterministic morphisms; for sources, $G=\Z$ acts by the shift. Call a
morphism $f\colon X\to Y$ \term{invariant} if $f\circ g=f$ for all $g\in G$. Let $X_{\mathrm{inv}}$ be the set $X$ with
the $\sigma$-algebra of invariant sets and $q\colon X\to X_{\mathrm{inv}}$ the map that is the identity on points.

\begin{theorem}[Moss--Perrone]\label{thm:MP}
\Sli[\cite{MP23}; see also \cite{EP23}]
\begin{enumerate}[label=(\roman*)]
\item $q\colon X\to X_{\mathrm{inv}}$ is the universal invariant morphism out of $X$: it is the colimit, in $\Stoch$,
of the diagram given by the action.
\item An invariant state $p$ on $X$ is ergodic iff $q\circ p$ is a deterministic state.
\item In a Markov category with conditionals in which the colimit in \textup{(i)} exists and satisfies a
compatibility condition, every invariant state $p$ is a mixture of ergodic ones: the conditional
$k\colon X_{\mathrm{inv}}\to X$ of $p$ given $q$ satisfies $p=k\circ(q\circ p)$, and $k$ is, almost surely with
respect to $q\circ p$, an ergodic invariant state.
\end{enumerate}
The proof of \textup{(iii)} is a short string-diagram argument that uses no limiting procedure and does not
depend on the cardinality of $G$.
\end{theorem}

Part (ii) is the classical definition read in $\Stoch$, where the deterministic states are exactly the
$\{0,1\}$-valued measures. Part (iii) recovers \cref{thm:decomposition} for standard Borel $X$. What the
formulation adds is a statement of where the decomposition comes from. It is the disintegration of $p$ over
the invariant quotient, and the ergodic components are the fibres. The space $X_{\mathrm{inv}}$ is usually not
standard Borel, which is one reason to work in $\Stoch$ and not in $\BorelStoch$ here.

The same quotient organizes the ergodic theorem. On $L^2(\mu)$ the composite of $q$ with its Bayesian
inverse is the conditional expectation onto invariant functions, and \cref{thm:birkhoff} says that time
averages converge to it. We return to this in \cref{ch:martingales}.

\section{Entropy is affine}

The entropy of a finite scheme is a strictly concave function of the distribution. The entropy of a source
is not.

\begin{theorem}\label{thm:affine}
\Scl[\cite{Jac59,Par61}] The function $H\colon M_T(A)\to[0,\log|A|]$ is affine and upper semicontinuous, and
\[ H(\mu)=\int H(\mu_e)\,d\lambda(e) \]
for the ergodic decomposition of $\mu$.
\end{theorem}

\begin{proof}
Let $\mu=\lambda\mu'+(1-\lambda)\mu''$. The block law $\mu_n$ is the same mixture of $\mu'_n$ and $\mu''_n$, and by
concavity of $H$ and \cref{prop:convexlinear},
\[ \lambda H_n(\mu')+(1-\lambda)H_n(\mu'')\ \le\ H_n(\mu)\ \le\ \lambda H_n(\mu')+(1-\lambda)H_n(\mu'')+\hb(\lambda). \]
Divide by $n$ and let $n\to\infty$. For semicontinuity, $H=\inf_nH_n/n$ by \cref{prop:rate}, and each $H_n$ is
continuous, depending on finitely many cylinder probabilities. An affine upper semicontinuous function on a
Choquet simplex satisfies the barycentric formula.
\end{proof}

The term $\hb(\lambda)$ is the entropy of the choice between the two components. It is paid once, and its
contribution per letter vanishes. This is the first instance of something that recurs: passing to rates
turns a concave function into an affine one, and more generally removes whatever is not extensive.

\begin{corollary}\label{cor:sup}
\Scl For an affine upper semicontinuous function on $M_T(A)$, the supremum over all stationary sources is
attained and equals the supremum over ergodic sources.
\end{corollary}

Khinchin defines the capacity of a channel as a supremum over ergodic sources and calls it the ergodic
capacity, leaving open whether a supremum over all stationary sources would be larger. The corollary
reduces that question to showing that the rate of transmission is affine and upper semicontinuous in the
source (\cref{ch:channels}).

\section{An example}

\begin{example}\label{ex:mixture}
Let $\mu$ be the equal mixture of two sources of independent bits, one with $\Prob(1)=0.1$ and one with
$\Prob(1)=0.5$. It is stationary and not ergodic: the limiting frequency of ones is an invariant function
taking two values. By \cref{thm:affine},
\[ H(\mu)=\tfrac12\bigl(\hb(0.1)+1\bigr)\approx0.7345. \]
The normalized block entropies $H_n/n$ are $0.8106$, $0.7445$, $0.7355$ for $n=10,100,1000$; the excess over
the limit is at most $1/n$. But a typical long block does not have probability near $2^{-0.7345\,n}$. With
probability $\tfrac12$ it comes from the first component and has probability near $2^{-0.469\,n}$, and with
probability $\tfrac12$ it comes from the second and has probability near $2^{-n}$. The entropy is the average
of two rates, and no long block exhibits it.
\end{example}

The example shows what McMillan's theorem must assume. For a non-ergodic source the quantity
$-\frac1n\log\mu_n(x_1\dots x_n)$ still converges, but to a random variable, the entropy of the ergodic component
that produced $x$.

\section*{Notes}

For ergodic theory see \cite{Wal82,Pet83}; for its use in information theory, \cite{Gra09,Gra11,Bil65}.
Khinchin's treatment is \cite[\S4]{Khi56}. The categorical ergodic decomposition is due to Moss and Perrone
\cite{MP23}, with further development by Ensarguet and Perrone \cite{EP23}; the synthetic zero--one laws
of \cite{FR20} give another route to \cref{prop:iid}. Affinity of the entropy rate and its integral
representation are due to Jacobs \cite{Jac59}; the corresponding statements for the rate of transmission
are due to Parthasarathy \cite{Par61} and Breiman \cite{Bre60}.

\section*{Exercises}

\begin{exercise}
Let $Q$ be a stochastic matrix with exactly two closed irreducible classes and no transient states. Show
that the stationary Markov sources with matrix $Q$ form a segment, that its endpoints are ergodic, and that
the entropy is an affine function on it.
\end{exercise}

\begin{exercise}\label{exer:cylinders}
Show that a stationary source is ergodic iff for all cylinders $C,C'$,
$\frac1n\sum_{k=0}^{n-1}\mu(C\cap T^{-k}C')\to\mu(C)\mu(C')$.
\end{exercise}

\begin{exercise}
Prove the two inequalities for $H_n(\mu)$ in the proof of \cref{thm:affine}, and show by an example that
the upper one can be an equality for every $n$.
\end{exercise}

\begin{exercise}\label{exer:mixlimit}
For the source of \cref{ex:mixture} show that $-\frac1n\log\mu_n(x_1\dots x_n)$ converges almost surely to a random
variable taking the values $\hb(0.1)$ and $1$ with probability $\tfrac12$ each.
\end{exercise}

\begin{exercise}
Let $\mu$ give probability $\tfrac12$ to each of the two sequences of alternating bits. Show that $\mu$ is
ergodic for $T$ and not for $T^2$, and that its entropy is zero.
\end{exercise}
%% ---- end ch/06-ergodic.tex ----
%% ---- begin ch/07-martingales.tex ----
\chapter{Martingales}\label{ch:martingales}

To prove McMillan's theorem Khinchin needs to know that the conditional probability of the next letter given
the last $n$ letters converges as $n\to\infty$. He obtains this from Doob's martingale convergence theorem,
to which he devotes a section. This chapter looks at the same convergence from the side of the category of
probability spaces. Conditioning on a $\sigma$-algebra is an idempotent morphism, a filtration is an
increasing sequence of idempotents, and the convergence of a martingale in mean is the convergence of that
sequence to its supremum. The same picture contains the mean ergodic theorem. What it does not contain is
almost sure convergence, and we say so.

\section{The setting}

Let $(X,\FF,p)$ be a probability space. A \term{filtration} is an increasing sequence of sub-$\sigma$-algebras
$\FF_1\subseteq\FF_2\subseteq\cdots$, and $\FF_\infty$ is the $\sigma$-algebra they generate. A \term{martingale} is a
sequence of integrable functions $M_n$, with $M_n$ measurable for $\FF_n$ and $\E[M_{n+1}\st\FF_n]=M_n$. It is
\term{closed} if $M_n=\E[f\st\FF_n]$ for a single integrable $f$.

For a stationary source and a letter $a$, let $\FF_n$ be generated by $x_{-n},\dots,x_{-1}$. Then
\[ M^a_n(x)=\mu(x_0=a\st x_{-n},\dots,x_{-1})=\E\bigl[1_{\{x_0=a\}}\st\FF_n\bigr] \]
is a closed martingale with values in $[0,1]$. This is the object Khinchin studies.

\section{Probability spaces and kernels}

\begin{definition}\label{def:krn}
$\Krn$ is the category whose objects are standard Borel probability spaces $(X,p)$ and whose morphisms
$(X,p)\to(Y,q)$ are Markov kernels $k$ with $k\circ p=q$, two kernels being identified when they agree
$p$-almost surely.
\end{definition}

A morphism of $\Krn$ is the same as a \term{coupling} of $p$ and $q$, the joint law $p\rtimes k$ on $X\times Y$.
Reading the coupling from the other side gives the Bayesian inverse $k^\dagger\colon(Y,q)\to(X,p)$.

\begin{proposition}\label{prop:dagger}
\Sli[\cite{CJ19,Fri20,DDGK16}] Bayesian inversion makes $\Krn$ a dagger category:
$k^{\dagger\dagger}=k$, $(l\circ k)^\dagger=k^\dagger\circ l^\dagger$, $\id^\dagger=\id$. For each $r\in[1,\infty]$ there is a
functor $L^r\colon\Krn^{\op}\to\Ban$ to Banach spaces and contractions, sending $(X,p)$ to $L^r(p)$ and $k$ to
$(k^*g)(x)=\int g(y)\,k(dy\st x)$. For $r=2$ it lands in Hilbert spaces and preserves daggers:
$(k^\dagger)^*=(k^*)^\dagger$.
\end{proposition}

A measure-preserving map $f\colon(X,p)\to(Y,q)$ is a morphism of $\Krn$, and $f^*g=g\circ f$ is an isometric
embedding. Since $f$ is deterministic, $f\circ f^\dagger=\id_Y$. The other composite
\[ e_f=f^\dagger\circ f\colon(X,p)\to(X,p) \]
is therefore idempotent and self-adjoint, $e_f\circ e_f=e_f=e_f^\dagger$. As a kernel it does this: given $x$,
forget everything except $f(x)$, and draw a new point from the conditional distribution given $f(x)$.

\begin{proposition}[Conditional expectations are idempotents]\label{prop:idem}
\Sli[\cite{PVB24}]
\begin{enumerate}[label=(\roman*)]
\item Every sub-$\sigma$-algebra $\GG\subseteq\FF$ arises, up to null sets, from a measure-preserving map
$f$, and so defines a dagger idempotent $e_\GG=e_f$ on $(X,p)$ that splits through a deterministic map.
\item $L^r$ sends $e_\GG$ to the conditional expectation $\E[\,\cdot\st\GG]$; for $r=2$ this is the orthogonal
projection onto $L^2(\GG)$.
\item $\GG\subseteq\GG'$ iff $e_\GG\circ e_{\GG'}=e_\GG$, and then also $e_{\GG'}\circ e_\GG=e_\GG$.
\end{enumerate}
\end{proposition}

Part (iii) is the tower property $\E[\E[f\st\GG']\st\GG]=\E[f\st\GG]$. It defines a partial order on the
idempotents, and a filtration is an increasing sequence $e_1\le e_2\le\cdots$ for it. A closed martingale is
the image of one function under the sequence of projections $L^r(e_n)$.

\section{Convergence in mean}

\begin{theorem}\label{thm:projections}
\Scl Let $P_1\le P_2\le\cdots$ be an increasing sequence of orthogonal projections on a Hilbert space. Then
$P_nv\to P_\infty v$ for every vector $v$, where $P_\infty$ is the projection onto the closure of the union of the
ranges. A decreasing sequence converges in the same sense to the projection onto the intersection of the
ranges.
\end{theorem}

\begin{proof}
If $v$ lies in the range of some $P_m$ then $P_nv=v$ for $n\ge m$. If $v$ is orthogonal to all the ranges then
$P_nv=0$. Such vectors span a dense subspace and $\|P_n\|\le1$. For a decreasing sequence apply this to
$1-P_n$.
\end{proof}

\begin{corollary}[L\'evy's theorems, in mean]\label{cor:levy}
\Scl Let $1\le r<\infty$ and $f\in L^r(p)$. If $\FF_n$ increases to $\FF_\infty$ then
$\E[f\st\FF_n]\to\E[f\st\FF_\infty]$ in $L^r$. If $\FF_n$ decreases to $\FF_{-\infty}=\bigcap_n\FF_n$ then
$\E[f\st\FF_n]\to\E[f\st\FF_{-\infty}]$ in $L^r$.
\end{corollary}

\begin{proof}
For $r=2$ this is \cref{thm:projections} with $P_n=\E[\,\cdot\st\FF_n]$, since $\bigcup_nL^2(\FF_n)$ is dense in
$L^2(\FF_\infty)$. For bounded $f$ the $L^2$ convergence together with the uniform bound $\|f\|_\infty$ gives $L^r$
convergence for every finite $r$. Bounded functions are dense in $L^r$ and conditional expectations are
contractions of $L^r$.
\end{proof}

So the convergence of closed martingales in mean takes a few lines once conditional expectation is seen as
a projection. Perrone and Van Belle show that the same argument can be run one level up, in the category
itself.

\begin{theorem}[Perrone--Van Belle]\label{thm:PVB}
\Sli[\cite{PVB24}] The categories $\Krn$ and $\Hilb$ are enriched in topological spaces in such a way that
\begin{enumerate}[label=(\roman*)]
\item every monotone net of dagger idempotents converges, in the topology of the hom-space, to its supremum
if it is increasing and to its infimum if it is decreasing;
\item the functors $L^r$, $1\le r<\infty$, are enriched, that is, continuous on hom-spaces.
\end{enumerate}
Consequently martingales and backward martingales indexed by arbitrary directed sets converge in $L^r$, and
the same holds for vector-valued martingales with any enriched functor in place of $L^r$.
\end{theorem}

The content of (i) for $\Krn$ is that the kernels $e_n$ themselves converge: the conditional distributions
given $\FF_n$ converge to the conditional distribution given $\FF_\infty$, in a topology that makes
integration against bounded functions continuous in $L^1$. A martingale is one function watched through
this convergence. For the source, the kernels are ``the law of $x_0$ given the last $n$ letters'', and the
limit is the law of $x_0$ given the infinite past.

\section{Almost sure convergence}

\begin{theorem}[Doob]\label{thm:doob}
\Scl[\cite{Doo53}] A martingale with $\sup_n\E|M_n|<\infty$ converges almost surely. In particular, in both
cases of \cref{cor:levy} the convergence holds almost surely as well.
\end{theorem}

This is the theorem Khinchin quotes. Its proof needs an inequality that controls all times at once, either
Doob's upcrossing inequality or the maximal inequality
$\Prob(\sup_n|M_n|>t)\le t^{-1}\sup_n\E|M_n|$. Nothing in \cref{thm:projections} or \cref{thm:PVB} supplies it.
This is the usual division of labour in analysis: convergence in norm comes from density and uniform
boundedness, almost everywhere convergence from a maximal inequality. The categorical methods available
at present reach the first and not the second. For the theorem we are aiming at this does not matter,
because McMillan's theorem as Khinchin states it is a statement about convergence in mean, and we shall
prove it in \cref{ch:aep} without \cref{thm:doob}.

\section{Limits against colimits}

A filtration gives two diagrams of Banach spaces: the inclusions $L^r(\FF_n)\hookrightarrow L^r(\FF_{n+1})$, and
the conditional expectations $L^r(\FF_{n+1})\twoheadrightarrow L^r(\FF_n)$ in the opposite direction. Work in
the category of Banach spaces and contractions, where a limit of a sequence consists of the bounded
compatible families.

\begin{proposition}\label{prop:limcolim}
\Sob Let $\FF_n$ increase to $\FF_\infty$.
\begin{enumerate}[label=(\roman*)]
\item For $1\le r<\infty$, $L^r(\FF_\infty)$ is the colimit of the inclusions.
\item The limit of the conditional expectations is the space of $L^r$-bounded martingales, with norm
$\sup_n\|M_n\|_r$.
\item For $1<r<\infty$ the map $f\mapsto(\E[f\st\FF_n])_n$ from the colimit to the limit is an isometric
isomorphism.
\item For $r=1$ it is isometric and in general not surjective. For the filtration generated by a sequence
of fair coin tosses, the limit is the space of all finite signed measures on the sequence space, and the
image of the colimit is the subspace of measures absolutely continuous with respect to the coin-tossing
measure.
\end{enumerate}
\end{proposition}

\begin{proof}
(i) is the density used in \cref{cor:levy}. (ii) is the definition of a martingale. (iii) is the classical
fact that for $r>1$ an $L^r$-bounded martingale is closed, with $\|f\|_r=\sup_n\|\E[f\st\FF_n]\|_r$. (iv) On a finite
$\sigma$-algebra an integrable function is the density of a signed measure, and a martingale is a
compatible family of signed measures on the algebras of cylinders with bounded total variation, which
extends uniquely to a signed measure on the sequence space. Closed martingales correspond to measures with a
density.
\end{proof}

For $r=2$ the inclusions and the conditional expectations are adjoint to each other, and (iii) is the
statement that for a sequence of embedding--projection pairs the colimit of the embeddings is the limit of
the projections. The same coincidence, for a different kind of object, is what makes recursive domain
equations solvable \cite{SP82}. For $r=1$ it fails, and the failure is the Lebesgue decomposition: the
martingales that do not come from a function on $\FF_\infty$ are the singular measures. The likelihood ratio of a
biased coin against a fair one is the standard example (\cref{exer:likelihood}).

\section{The mean ergodic theorem}

\begin{theorem}[von Neumann]\label{thm:vN}
\Scl[\cite{vN32}] Let $U$ be an isometry of a Hilbert space and $P$ the orthogonal projection onto the space
$\Fix(U)$ of invariant vectors. Then $\frac1n\sum_{k=0}^{n-1}U^kv\to Pv$ for every $v$.
\end{theorem}

\begin{proof}
First $\Fix(U)=\Fix(U^*)$: if $Uv=v$ then
$\|U^*v-v\|^2=\|U^*v\|^2-2\operatorname{Re}\langle v,Uv\rangle+\|v\|^2\le0$, and symmetrically. Hence the orthogonal complement of
$\Fix(U)$ is the closure of the range of $1-U$. On $\Fix(U)$ the averages are constant. On a vector
$w-Uw$ they equal $(w-U^nw)/n$, which tends to zero. The averages are contractions, so the convergence
extends to the closure.
\end{proof}

\begin{corollary}\label{cor:meanergodic}
\Scl Let $\mu$ be a stationary source and $f\in L^1(\mu)$. Then $\frac1n\sum_{k<n}f\circ T^k\to\E[f\st\II]$ in $L^1$.
\end{corollary}

\begin{proof}
$Uf=f\circ T$ is an isometry of $L^2(\mu)$ whose invariant vectors are the $\II$-measurable functions. For
$f\in L^2$ apply \cref{thm:vN}; $L^2$ is dense in $L^1$ and the averages are contractions of $L^1$.
\end{proof}

In the language of this chapter the limit is again an idempotent. Let $q\colon X\to X_{\mathrm{inv}}$ be the
invariant quotient of \cref{thm:MP}. Then $e_\II=q^\dagger\circ q$ is the dagger idempotent of the invariant
$\sigma$-algebra, and the corollary says that the Ces\`aro averages of the powers of $T$ converge to it
under $L^1$.

We now have two convergence statements of the same form. Along a filtration, an increasing sequence of
idempotents converges to its supremum. Along time, the averages of an automorphism converge to the
idempotent of its invariants. The first is an instance of \cref{thm:PVB}. The second is not, since the
averages are not idempotents and do not form a monotone net; whether it has a proof internal to an
enriched dagger Markov category is a question we return to in \cref{ch:coda}.

\section*{Notes}

Khinchin's section on martingales is \cite[\S6]{Khi56}, after Doob \cite{Doo53}. The dagger structure on
categories of probability spaces is discussed in \cite{CJ19,Fri20,DDGK16}. The treatment of conditional
expectations as idempotents and \cref{thm:PVB} are due to Perrone and Van Belle \cite{PVB24}; see also Van
Belle \cite{VB23}. The proof of the mean ergodic theorem given here is F.~Riesz's.

\section*{Exercises}

\begin{exercise}
Let $X=\{1,\dots,6\}$ with the uniform distribution and let $\GG$ be generated by the partition
$\{1,2\}\,|\,\{3,4,5,6\}$. Write $e_\GG$ as a stochastic matrix, check that it is idempotent and symmetric, and
compute its action on $f(x)=x$.
\end{exercise}

\begin{exercise}
Prove \cref{prop:idem}(iii). Give two $\sigma$-algebras on a three-point space whose idempotents do not commute.
\end{exercise}

\begin{exercise}
On $[0,1)$ with Lebesgue measure let $\FF_n$ be generated by the dyadic intervals of length $2^{-n}$ and let
$f(x)=x$. Compute $\E[f\st\FF_n]$ and show that $\|f-\E[f\st\FF_n]\|_2=2^{-n}/\sqrt{12}$.
\end{exercise}

\begin{exercise}\label{exer:likelihood}
Let $x_1,x_2,\dots$ be fair coin tosses and $M_n=\prod_{k\le n}2\theta^{x_k}(1-\theta)^{1-x_k}$ with $\theta=0.8$. Show that
$M_n$ is a martingale with $\E M_n=1$ and that $\E\sqrt{M_n}=\rho^n$ with
$\rho=\tfrac12(\sqrt{1.6}+\sqrt{0.4})\approx0.949$. Deduce that $M_n\to0$ in probability and that $M_n$ is not
closed.
\end{exercise}

\begin{exercise}
Let $U$ be the permutation matrix of $\sigma=(1\,2\,3)(4\,5)$ acting on functions on $\{1,\dots,5\}$. Compute
$\frac16\sum_{k<6}U^k$ and identify it with a conditional expectation.
\end{exercise}
%% ---- end ch/07-martingales.tex ----
%% ---- begin ch/08-aep.tex ----
\chapter{McMillan's Theorem}\label{ch:aep}

McMillan's theorem says that for an ergodic source almost all long blocks have about the same probability,
$2^{-nH}$. Shannon proved it for independent letters and for Markov chains, where it is the law of large
numbers, and Khinchin's first paper follows him. The general case is due to McMillan, and proving it
carefully is the main task of the second chapter of Khinchin's second paper, which takes some thirty pages
and rests on the theorems of Birkhoff and Doob. With the preparation of the last two chapters the proof is
short, and it shows what the theorem depends on: the chain rule, two convergence statements about
idempotents, and one elementary estimate.

\section{The statement}

For a stationary source $\mu$ and $n\ge1$ let
\[ i_n(x)=-\log\mu_n(x_0\dots x_{n-1}) \]
be the \term{information} of the first $n$ letters. Its expectation is the block entropy $H_n$.

\begin{definition}[Khinchin]
A source has the \term{$E$ property} if $\frac1ni_n\to H(\mu)$ in probability: for all $\varepsilon,\delta>0$
and all large $n$, the blocks $C$ of length $n$ with $|-\frac1n\log\mu_n(C)-H(\mu)|\le\varepsilon$ have total
probability more than $1-\delta$.
\end{definition}

\begin{theorem}[McMillan]\label{thm:mcmillan}
\Scl[\cite{McM53,Khi56}] For an ergodic source, $\frac1ni_n\to H(\mu)$ in $L^1(\mu)$. In particular every ergodic
source has the $E$ property. For a stationary source, $\frac1ni_n$ converges in $L^1$ to the entropy
$H(\mu_x)$ of the ergodic component of $x$.
\end{theorem}

\section{Information as a sum over time}

Let $\FF_k$ be generated by $x_{-k},\dots,x_{-1}$, with $\FF_0$ trivial and $\FF_\infty$ generated by the whole past.
For $0\le k\le\infty$ put
\[ g_k(x)=-\log\mu(x_0\st\FF_k)(x), \]
the information of the present letter given the last $k$ letters. In the notation of \cref{ch:martingales},
$g_k=-\log M_k^{x_0}$.

\begin{lemma}\label{lem:timesum}
\Scl $i_n=\sum_{k=0}^{n-1}g_k\circ T^k$, and $\E g_k=c_k$, the increment of \cref{prop:rate}.
\end{lemma}

\begin{proof}
$\mu_n(x_0\dots x_{n-1})=\prod_{k<n}\mu(x_k\st x_0,\dots,x_{k-1})$, and by stationarity the $k$-th factor is
$\mu(x_0\st\FF_k)$ evaluated at $T^kx$.
\end{proof}

This is the chain rule of \cref{ch:schemes} spread along the time axis. If the summands were one function
$g$ composed with the powers of $T$, the ergodic theorem would finish the proof. They are not, but they
converge.

\begin{lemma}\label{lem:tail}
\Scl For every $0\le k\le\infty$ and $t\ge0$,
\[ \mu\{g_k>t\}\le|A|\,2^{-t}. \]
Consequently $\sup_k\E[g_k^2]<\infty$, and $\mu(x_0\st\FF_\infty)>0$ almost surely.
\end{lemma}

\begin{proof}
For a letter $a$ and $s=2^{-t}$,
\[ \mu\{x_0=a,\ M_k^a\le s\}=\E\bigl[1_{\{M_k^a\le s\}}\,\E[1_{\{x_0=a\}}\st\FF_k]\bigr]=\E\bigl[1_{\{M_k^a\le s\}}M_k^a\bigr]\le s. \]
Sum over $a$. The second moment is $\int_0^\infty2t\,\mu\{g_k>t\}\,dt$.
\end{proof}

\begin{lemma}\label{lem:gk}
\Scl $g_k\to g_\infty$ in $L^1$, and $\E g_\infty=H(\mu)$.
\end{lemma}

\begin{proof}
By \cref{cor:levy}, $M_k^a\to M_\infty^a$ in $L^1$ for each letter, so $M_k^{x_0}\to M_\infty^{x_0}$ in probability. The limit is
almost surely positive by \cref{lem:tail} and $-\log$ is continuous on $(0,1]$, so $g_k\to g_\infty$ in
probability. A sequence bounded in $L^2$ is uniformly integrable, so the convergence is in $L^1$. Then
$\E g_\infty=\lim\E g_k=\lim c_k=H(\mu)$.
\end{proof}

\section{Proof of the theorem}

\begin{proof}[Proof of \cref{thm:mcmillan}]
Since $T$ preserves $\mu$, \cref{lem:timesum} gives
\[ \Bigl\|\frac1ni_n-\frac1n\sum_{k<n}g_\infty\circ T^k\Bigr\|_1\le\frac1n\sum_{k<n}\|g_k-g_\infty\|_1, \]
which tends to zero by \cref{lem:gk}. By the mean ergodic theorem (\cref{cor:meanergodic}),
$\frac1n\sum_{k<n}g_\infty\circ T^k\to\E[g_\infty\st\II]$ in $L^1$. If $\mu$ is ergodic this is the constant
$\E g_\infty=H(\mu)$. In general it is an invariant function whose integral over each ergodic component is the
entropy of that component.
\end{proof}

The argument used four things. The chain rule put $i_n$ in the form of \cref{lem:timesum}. L\'evy's theorem in
mean, which is the convergence of an increasing sequence of idempotents (\cref{thm:projections}), gave the
convergence of the conditional laws. The mean ergodic theorem, which is the convergence of time averages to
the invariant idempotent (\cref{thm:vN}), gave the limit. \Cref{lem:tail} supplied the uniform integrability
needed to pass from conditional probabilities to their logarithms. Doob's almost sure theorem and
Birkhoff's were not used. This organization of the proof is certainly known to specialists; we set it out
because it isolates how little of the measure theory in Khinchin's proof is specific to the problem.

\begin{remark}\label{rem:twoidem}
The limit can be written in one line. Let $e_{\mathrm{past}}$ be the idempotent of the $\sigma$-algebra
generated by the past and $e_\II$ that of the invariant sets. The first determines the conditional law of
$x_0$ given the past, hence the function $g_\infty$; the second is applied to it:
\[ \lim_n\tfrac1ni_n=L^1(e_\II)\,g_\infty. \]
The entropy of an ergodic source is the time average of the information of the present given the past.
\end{remark}

\section{The almost sure theorem}

\begin{theorem}[Shannon--McMillan--Breiman]\label{thm:SMB}
\Scl[\cite{Bre57,Chu61,AC88}] For an ergodic source, $\frac1ni_n\to H(\mu)$ almost surely. The same holds for
countable alphabets when $H_1<\infty$.
\end{theorem}

Breiman's proof combines the almost sure forms of the two convergence theorems with a maximal inequality
for $\sup_kg_k$, of which \cref{lem:tail} is the distributional part; Algoet and Cover later gave a proof by
sandwiching $i_n$ between Markov approximations. The theorem extends to actions of amenable groups
\cite{OW83,Lin01}. For the coding theorems convergence in probability is all that is needed.

\section{Typical sets and the counting theorem}

Fix $\varepsilon>0$ and let $T_n^\varepsilon$ be the set of blocks $C$ of length $n$ with
$2^{-n(H+\varepsilon)}\le\mu_n(C)\le2^{-n(H-\varepsilon)}$, where $H=H(\mu)$.

\begin{corollary}\label{cor:typical}
\Scl For an ergodic source, $\mu_n(T_n^\varepsilon)\to1$; $|T_n^\varepsilon|\le2^{n(H+\varepsilon)}$ for all $n$; and
$|T_n^\varepsilon|\ge(1-\delta)\,2^{n(H-\varepsilon)}$ as soon as $\mu_n(T_n^\varepsilon)\ge1-\delta$.
\end{corollary}

For $0<\lambda<1$ let $N_n(\lambda)$ be the least number of blocks of length $n$ whose total probability is at
least $\lambda$.

\begin{theorem}[Khinchin's Theorem 3]\label{thm:counting}
\Scl[\cite{Sha48,Khi53}] For an ergodic source and every $\lambda\in(0,1)$,
\[ \lim_{n\to\infty}\frac1n\log N_n(\lambda)=H(\mu). \]
\end{theorem}

\begin{proof}
For large $n$ the typical set has probability at least $\lambda$, so $N_n(\lambda)\le2^{n(H+\varepsilon)}$. Conversely let
$S$ have probability at least $\lambda$. For large $n$, $\mu_n(S\cap T_n^\varepsilon)\ge\lambda/2$, and each block in
$T_n^\varepsilon$ has probability at most $2^{-n(H-\varepsilon)}$, so $|S|\ge\frac\lambda2\,2^{n(H-\varepsilon)}$.
\end{proof}

The limit does not depend on $\lambda$. That is the remarkable part of the statement, and it is special to
the ergodic case.

\begin{example}\label{ex:counting}
For independent bits with $\Prob(1)=0.2$ the entropy is $\hb(0.2)\approx0.7219$. The typical set with
$\varepsilon=0.05$ has probability $0.468$ at $n=100$ and $0.952$ at $n=1000$. The rates $\frac1n\log N_n(\lambda)$
are:
\begin{center}\small
\begin{tabular}{@{}lccc@{}}
\toprule
 & $\lambda=0.1$ & $\lambda=0.5$ & $\lambda=0.9$\\\midrule
$n=100$ & $0.571$ & $0.684$ & $0.779$\\
$n=1000$ & $0.683$ & $0.717$ & $0.748$\\
\bottomrule
\end{tabular}
\end{center}
The spread across $\lambda$ shrinks like $1/\sqrt n$ (\cref{exer:second}). For the Markov source of
\cref{ex:markov}, $\E|\frac1ni_n-H|$ is $0.447$, $0.216$, $0.109$ at $n=4,16,64$.
\end{example}

\begin{example}\label{ex:mixcount}
For the non-ergodic source of \cref{ex:mixture} the limit depends on $\lambda$. At $n=1000$ the rate
$\frac1n\log N_n(\lambda)$ is $0.463$ for $\lambda=0.25$ and $0.999$ for $\lambda=0.75$; the limits are $\hb(0.1)\approx0.469$ and $1$
(\cref{exer:mixcount}). The entropy $0.7345$ of the source is not the answer to any counting question.
\end{example}

So for a stationary source that is not ergodic, the entropy rate is not an operational quantity. The number
of bits per letter needed to describe all but a fraction $\varepsilon$ of the blocks is a quantile of the
distribution of $H(\mu_x)$, and to make $\varepsilon$ arbitrarily small one needs the essential supremum. This
is the starting point of the information-spectrum method \cite{HV93,Han03}. Khinchin's restriction to ergodic
sources is therefore not a convenience. His Theorem~4, on the best compression of a text by codes that may fail on a set of
small probability, is false without it. For codes of variable length judged by their expected length the
entropy rate remains the answer for every stationary source (\cref{ch:shannon}).

\section{The theorem as a statement about retractions}

\begin{definition}\label{def:compression}
Let $(X,p)$ be a finite probability space and $0<\varepsilon<1$. An \term{$(M,\varepsilon)$-compression} of
$(X,p)$ is a pair of maps $e\colon X\to[M]$ and $d\colon[M]\to X$, where $[M]=\{1,\dots,M\}$, such that
$d(e(x))=x$ with probability at least $1-\varepsilon$. Let $M_*(p,\varepsilon)$ be the least $M$ for which one
exists.
\end{definition}

When $\varepsilon=0$ and $p$ has full support this says that $X$ is a retract of $[M]$, which happens iff
$|X|\le M$. In general the set where $d\circ e$ is the identity has at most $M$ points, and any $M$ points
can be made such a set, so $M_*(p,\varepsilon)=N(1-\varepsilon)$ in the notation above.

\begin{proposition}\label{prop:corank}
\Srf[\cref{thm:counting}] For an ergodic source and every $\varepsilon\in(0,1)$,
\[ \lim_{n\to\infty}\frac1n\log M_*(\mu_n,\varepsilon)=H(\mu). \]
\end{proposition}

Up to $\varepsilon$, the space of blocks of length $n$ is a retract of a set with $2^{nH}$ points and of no
smaller one. Entropy is the exponential growth rate of the approximate cardinality of $A^n$ as seen by
$\mu$. In \cref{ch:feinstein} the dual notion, a finite set that is an approximate retract of a channel, will
define capacity, and the two will be composed in \cref{ch:shannon}.

McMillan's theorem says more than \cref{prop:corank}, since it controls the probabilities of the typical
blocks from both sides.

\begin{proposition}\label{prop:uniform}
\Scl Let $\mu$ be ergodic and $\varepsilon>0$. For large $n$ there is a set $S\subseteq A^n$ with
$\mu_n(S)\ge1-\varepsilon$ such that, for the uniform distribution $u_S$ on $S$ and all $C\in S$,
\[ \Bigl|\frac1n\log\frac{\mu_n(C)}{u_S(C)}\Bigr|\le2\varepsilon+\frac1n . \]
\end{proposition}

Thus $\mu_n$ is close to a uniform distribution, but only on the exponential scale: the ratio of
probabilities is $2^{o(n)}$, not close to $1$, and $\mu_n$ is in general far from $u_S$ in total variation.
Gromov has made this scale into a framework \cite{Gro13}. He considers the category of finite probability
spaces and measure-preserving maps, defines an asymptotic equivalence between sequences of such spaces
that ignores sets of small measure and subexponential factors, and reads the law of large numbers as the
statement that the powers $P^{\otimes n}$ are asymptotically equivalent to the uniform spaces on $2^{nH(P)}$
points. Entropy is then the isomorphism from the semigroup of asymptotic classes, under tensor product, to
$[0,\infty)$. McMillan's theorem extends the first half of this from powers of one space to the block laws of
any ergodic source.

\section*{Notes}

McMillan's theorem is \cite{McM53}; Khinchin's proof is \cite[\S\S5--8]{Khi56}. The almost sure version is
due to Breiman \cite{Bre57}, with the countable case by Chung \cite{Chu61}; the sandwich proof is
\cite{AC88}. Textbook accounts are in \cite{Bil65,Gra11,CT06}. The counting theorem and its use for coding
go back to Shannon \cite{Sha48}. The second-order behaviour in \cref{exer:second} is due to Strassen. For
the non-ergodic case and the information spectrum see \cite{Han03}.

\section*{Exercises}

\begin{exercise}
For independent letters with distribution $p$, derive the $E$ property from Chebyshev's inequality, with the
bound $\Prob(|\frac1ni_n-H|\ge\varepsilon)\le\sigma^2/(n\varepsilon^2)$ where $\sigma^2$ is the variance of $-\log p(x_0)$.
Compute $\sigma^2$ for bits with $\Prob(1)=0.2$.
\end{exercise}

\begin{exercise}
For a stationary Markov source show that $g_k=g_1$ for all $k\ge1$, and deduce McMillan's theorem from
\cref{cor:meanergodic} alone.
\end{exercise}

\begin{exercise}
Prove \cref{cor:typical} and \cref{prop:uniform}.
\end{exercise}

\begin{exercise}\label{exer:mixcount}
For the source of \cref{ex:mixture} show that $\frac1n\log N_n(\lambda)\to\hb(0.1)$ for $\lambda<\tfrac12$ and $\to1$ for
$\lambda>\tfrac12$.
\end{exercise}

\begin{exercise}\label{exer:second}
For independent bits with $\Prob(1)=p<\tfrac12$, show that $N_n(\lambda)$ is attained by a set of sequences with
the fewest ones, and use the central limit theorem to show that
\[ \frac1n\log N_n(\lambda)=\hb(p)+\frac{\sigma\,\Phi^{-1}(\lambda)}{\sqrt n}+o\Bigl(\frac1{\sqrt n}\Bigr),\qquad\sigma=\sqrt{p(1-p)}\,\log\frac{1-p}{p}, \]
where $\Phi$ is the standard normal distribution function. Compare with the table in \cref{ex:counting}.
\end{exercise}
%% ---- end ch/08-aep.tex ----
\part{Channels and Coding}
%% ---- begin ch/09-channels.tex ----
\chapter{Channels}\label{ch:channels}

A channel, for Khinchin, is a family of probability measures $\nu_x$ on output sequences, one for each input
sequence $x$. He imposes three conditions on it, stationarity, absence of anticipation and finite memory,
connects it to a source, and proves that the resulting compound source is stationary and, when the source
is ergodic, ergodic. In this chapter a channel is a morphism of the category $\Dyn$ of \cref{ch:sources}.
The first of Khinchin's theorems becomes the statement that morphisms compose. The second is false as he
states it, as was noticed within a few years, and the categorical formulation shows where the missing
hypothesis has to go. We then study capacity as a function on morphisms.

\section{Khinchin's definitions}

\begin{definition}[\cite{Khi56}, \S9]\label{def:channel}
A \term{channel} $[A,\nu,B]$ with input alphabet $A$ and output alphabet $B$ is a Markov kernel
$\nu\colon\AZ\to\BZ$. It is
\begin{itemize}
\item \term{stationary} if $\nu\circ T=T\circ\nu$, that is, $\nu_{Tx}(TS)=\nu_x(S)$;
\item \term{without anticipation} if for every $n$ the law of $(\dots,y_{n-1},y_n)$ under $\nu_x$ depends
only on $(\dots,x_{n-1},x_n)$;
\item of \term{finite memory} $m$ if for all $s\le t$ the law of $(y_s,\dots,y_t)$ under $\nu_x$ depends only on
$(x_{s-m},\dots,x_t)$.
\end{itemize}
\end{definition}

A \term{memoryless} channel is given by a stochastic matrix $W\colon A\to B$ and
$\nu_x=\bigotimes_nW(\,\cdot\st x_n)$: the output letters are independent given the input, and the $n$-th
depends on $x_n$ alone. It has all three properties with $m=0$.

\section{Connecting a channel to a source}

By \cref{prop:dyn}, a stationary channel is a morphism $(\AZ,T)\to(\BZ,T)$ of $\Dyn$ and a stationary source is a
state.

\begin{definition}
The \term{compound source} of a source $[A,\mu]$ and a channel $[A,\nu,B]$ is the state
\[ \omega=(\id\otimes\nu)\circ\cpy\circ\mu\quad\text{on }\AZ\times\BZ=(A\times B)^{\Z}, \]
that is, $\omega(M\times N)=\int_M\nu_x(N)\,d\mu(x)$. Its second marginal $\eta=\nu\circ\mu$ is the \term{output source}.
\end{definition}

\begin{figure}[ht]\centering
\begin{tikzpicture}[x=1cm,y=1cm]
  \node[ogbox] (mu) at (0,0) {$\mu$};
  \node[dec] (c) at (1.6,0) {};
  \node[ogbox] (nu) at (3.4,-0.65) {$\nu$};
  \node[ogbox] (T1) at (5.4,0.65) {$T$};
  \node[ogbox] (T2) at (5.4,-0.65) {$T$};
  \draw[fw] (mu) -- (c);
  \draw[fw] (c) |- (T1);
  \draw[fw] (c) |- (nu);
  \draw[fw] (nu) -- (T2);
  \draw[fw] (T1) -- (7.0,0.65);
  \draw[fw] (T2) -- (7.0,-0.65);
  \node at (-1.2,-2.9) {$=$};
  \node[ogbox] (mu2) at (0,-2.9) {$\mu$};
  \node[ogbox] (T3) at (1.9,-2.9) {$T$};
  \node[dec] (c2) at (3.5,-2.9) {};
  \node[ogbox] (nu2) at (5.4,-3.55) {$\nu$};
  \draw[fw] (mu2) -- (T3);
  \draw[fw] (T3) -- (c2);
  \draw[fw] (c2) |- (7.0,-2.25);
  \draw[fw] (c2) |- (nu2);
  \draw[fw] (nu2) -- (7.0,-3.55);
\end{tikzpicture}
\caption{The compound source and the proof that it is stationary. The shift slides through $\nu$ by
equivariance and through the copy node because it is deterministic; it is then absorbed by $\mu$.}\label{fig:hookup}
\end{figure}

\begin{theorem}[Khinchin]\label{thm:stationary}
\Srf[\cite{Khi56}, \S10] If the source and the channel are stationary, so are the compound source and the output
source.
\end{theorem}

\begin{proof}
$\cpy$ and $\nu$ are morphisms of $\Dyn$ and $\mu$ is a state, so $\omega$ is a state of $\Dyn$. Written out
(\cref{fig:hookup}),
\begin{align*}
 (T\otimes T)\circ(\id\otimes\nu)\circ\cpy\circ\mu&=(\id\otimes\nu)\circ(T\otimes T)\circ\cpy\circ\mu\\
 &=(\id\otimes\nu)\circ\cpy\circ T\circ\mu=\omega,
\end{align*}
using in turn the equivariance of $\nu$, the determinism of $T$, and the invariance of $\mu$.
\end{proof}

The same reasoning shows that channels compose: from $[A,\nu,B]$ and $[B,\nu',C]$ one gets $[A,\nu'\circ\nu,C]$,
stationary if both are. A stationary code is a deterministic channel, and coding a source before sending it
through a channel is composition. Khinchin uses all of this in his last chapter, where a code is treated
as a channel so that the previous theorems apply to it.

\section{Anticipation and naturality}

To see what absence of anticipation means, take one-sided time. The space $A^{\N}$ of sequences
$x_1x_2\dots$ is the limit of the tower $\cdots\to A^{n+1}\to A^n\to\cdots$ of maps forgetting the last letter.

\begin{proposition}\label{prop:natural}
\Srf A kernel $\nu\colon A^{\N}\to B^{\N}$ is without anticipation iff it is induced by a family of kernels
$\nu_n\colon A^n\to B^n$ in $\FinStoch$ that commutes with the maps of the two towers, a natural
transformation. The correspondence is bijective. A memoryless channel is the family $\nu_n=W^{\otimes n}$.
\end{proposition}

\begin{proof}
If $\nu$ is without anticipation, the law of $y_1\dots y_n$ is a function of $x_1\dots x_n$, which defines
$\nu_n$, and marginalizing $y_{n+1}$ gives naturality. Conversely a natural family composed with the
projections $A^{\N}\to A^n$ is a compatible family of kernels $A^{\N}\to B^n$, which by \cref{thm:kolmogorov} is a
kernel into $B^{\N}$.
\end{proof}

Natural transformations between towers of sets are the causal functions on streams, and they are the
morphisms between stream objects in the topos of trees, the presheaf category on the ordinal $\omega$
\cite{BMSS12}. The proposition is the stochastic version: channels without anticipation are natural
transformations of towers in $\FinStoch$. Among them the memoryless ones are those that are also
compatible with concatenation, $\nu_{m+n}=\nu_m\otimes\nu_n$. Memory of length $m$ lies in between.

\section{Ergodicity: a gap and its repair}

Khinchin's second theorem about the compound source reads: if the source is ergodic and the channel is
stationary, without anticipation and of finite memory, then the compound source is ergodic. He needs it
in order to apply McMillan's theorem to the compound source.

\begin{example}\label{ex:gap}
Let $\nu_x=\tfrac12\delta_{\mathbf0}+\tfrac12\delta_{\mathbf1}$ for every $x$, where $\mathbf0$ and $\mathbf1$ are the constant
sequences. This channel ignores its input and emits one random bit forever. It is stationary. It is
without anticipation and has memory $0$ in the sense of \cref{def:channel}, since the law of any output block
does not depend on $x$ at all. For any source, $\omega=\mu\otimes\nu$, and the set $\AZ\times\{\mathbf0\}$ is invariant
with probability $\tfrac12$. The compound source is not ergodic.
\end{example}

So the theorem fails under the stated hypotheses. Breiman noted that Khinchin's definition of finite memory
is not restrictive enough for his results, and Takano and Feinstein had by then added the missing
condition \cite{Bre60,Tak58,Fei59}.

\begin{definition}
A channel has \term{finite output memory} $m$ if, for every $x$, the blocks $(y_s,\dots,y_t)$ and
$(y_{s'},\dots,y_{t'})$ are independent under $\nu_x$ whenever $s'-t>m$.
\end{definition}

\begin{theorem}\label{thm:ergodicchannel}
\Scl[\cite{Tak58,Fei59,Adl61}] Let the channel be stationary, of finite memory in the sense of
\cref{def:channel} and of finite output memory. If the source is ergodic, the compound source and the output
source are ergodic.
\end{theorem}

\begin{proof}
Let $E=C\times D$ and $E'=C'\times D'$ be products of cylinders in $\AZ$ and $\BZ$. By finite memory
$f(x)=1_C(x)\,\nu_x(D)$ depends on finitely many coordinates of $x$, and likewise $f'$. For large $k$ the output
blocks defining $D$ and $T^{-k}D'$ are more than $m$ apart, so by finite output memory and stationarity
\[ \omega(E\cap T^{-k}E')=\int f(x)\,f'(T^kx)\,d\mu(x). \]
By the mean ergodic theorem the Ces\`aro averages of the right side converge to $\int f\,d\mu\int f'\,d\mu=\omega(E)\,\omega(E')$,
and this criterion on cylinders is equivalent to ergodicity (\cref{exer:cylinders}).
\end{proof}

The categorical picture explains the shape of the gap. By \cref{prop:cofree}, an equivariant map into $\BZ$ is
determined by its time-zero coordinate, but an equivariant kernel is not. A stationary channel consists of
the conditional laws of finite output blocks given the input, and of the way these fit together across
time. Khinchin's memory condition bounds the first, the dependence on the input. Ergodicity of the
composite is a statement about the second, and \cref{ex:gap} is a channel that is as trivial as possible in
the first respect and as bad as possible in the second. In $\Dyn$ the ergodic states are not preserved by
arbitrary morphisms; \cref{thm:ergodicchannel} describes a class of morphisms that do preserve them.
Deterministic morphisms always do, since a factor of an ergodic source is ergodic.

\section{Rate and capacity}

\begin{definition}[\cite{Khi56}, \S10]
For a stationary source and channel, the \term{rate of transmission} is
\[ R(\mu,\nu)=H(\mu)+H(\eta)-H(\omega)=\lim_{n\to\infty}\frac1n\,I(x_1\dots x_n;\,y_1\dots y_n). \]
The \term{ergodic capacity} $C$ of the channel is the supremum of $R(\mu,\nu)$ over ergodic sources $\mu$.
\end{definition}

Since $\mu\mapsto\eta$ and $\mu\mapsto\omega$ are affine, \cref{thm:affine} gives at once:

\begin{proposition}\label{prop:rateaffine}
\Scl[\cite{Par61}] For every stationary channel, $R(\,\cdot\,,\nu)$ is an affine function on the simplex of
stationary sources.
\end{proposition}

\begin{theorem}\label{thm:capacities}
\Scl[\cite{Bre60,Par61}] For a stationary channel of finite memory and finite output memory,
$R(\,\cdot\,,\nu)$ is upper semicontinuous. Hence the supremum over all stationary sources equals the ergodic
capacity, and it is attained by an ergodic source.
\end{theorem}

The second statement follows from the first by \cref{cor:sup}. It answers the question Khinchin leaves open
in his conclusion, where he remarks that capacity is usually defined carelessly and that his own definition
may give a smaller number than a supremum over all stationary sources. It does not.

\section{Memoryless channels}

For a stochastic matrix $W\colon A\to B$ and a distribution $p$ on $A$, write $I(p,W)$ for the mutual
information of the joint distribution $p\rtimes W$.

\begin{theorem}\label{thm:dmc}
\Scl[\cite{Sha48}] The capacity of the memoryless channel with matrix $W$ is
\[ C(W)=\max_pI(p,W), \]
attained by the source of independent letters with a maximizing distribution.
\end{theorem}

\begin{proof}
Given the input block, the output letters are independent, so
$I(x_1^n;y_1^n)=H(y_1^n)-\sum_kH(y_k\st x_k)\le\sum_kI(x_k;y_k)\le n\max_pI(p,W)$. Independent inputs give
equality.
\end{proof}

\begin{example}\label{ex:channels}
The binary symmetric channel with flip probability $\delta$ has $C=1-\hb(\delta)$; for $\delta=0.1$ this is
$0.531$. The binary erasure channel, which replaces its input by an erasure symbol with probability $e$,
has $C=1-e$. The Z-channel, which sends $0$ to $0$ and flips $1$ to $0$ with probability $\delta$, has
$C=\log\bigl(1+(1-\delta)\,\delta^{\delta/(1-\delta)}\bigr)$, which is $0.763$ for $\delta=0.1$.
\end{example}

\section{Capacity as a function on morphisms}

Restricted to memoryless channels, capacity is a function on the morphisms of $\FinStoch$.

\begin{proposition}\label{prop:capacity}
\Scl
\begin{enumerate}[label=(\roman*)]
\item $C(\id_X)=\log|X|$, and $C(W)=0$ iff $W$ factors through the one-point set.
\item $C(V\circ W)\le\min\{C(V),C(W)\}$.
\item $C(W\otimes W')=C(W)+C(W')$.
\item If $W$ factors through a set with $r$ elements, then $C(W)\le\log r$.
\end{enumerate}
\end{proposition}

\begin{proof}
(ii) For $X\to Y\to Z$ the data-processing inequality gives $I(X;Z)\le\min\{I(X;Y),I(Y;Z)\}$. (iii) Product
inputs give $\ge$; conversely for the product channel
$I(XX';YY')=H(YY')-H(Y\st X)-H(Y'\st X')\le I(X;Y)+I(X';Y')$. (iv) follows from (i) and (ii).
\end{proof}

These are the properties of the logarithm of the rank of a matrix: it is $\log n$ on the identity of an
$n$-dimensional space, it does not increase under composition, it is additive under tensor product, and
it is bounded by the logarithm of the dimension of anything the matrix factors through. Capacity is a
rank for stochastic matrices that is stable under small perturbations. The next chapter makes this exact:
capacity is the growth rate of the largest identity onto which the tensor powers of $W$ retract, up to
$\varepsilon$.

\begin{example}[A channel with memory]\label{ex:isi}
Let $A=B=\{0,1\}$ and $y_n=x_n\oplus x_{n-1}\oplus z_n$, where the $z_n$ are independent bits equal to $1$ with
probability $\delta$. This channel is stationary and without anticipation, has memory $1$, and has output
memory $0$, since the outputs are independent given the input. It is the composite of the sliding block
code $\phi(x)_n=x_n\oplus x_{n-1}$ with the memoryless binary symmetric channel, so its capacity is at most
$1-\hb(\delta)$ by the inequality above. Equality holds: $\phi$ maps independent fair bits to independent
fair bits, so the source of independent fair bits has rate of transmission $1-\hb(\delta)$. The memory costs
nothing here because $\phi$ is invertible up to one bit.
\end{example}

For channels with memory (ii) persists in the form $R(\mu,\nu'\circ\nu)\le\min\{R(\mu,\nu),R(\nu\circ\mu,\nu')\}$, by the same
inequality applied to blocks.

\section{Joinings and the backward channel}

The compound source $\omega$ is a stationary measure on $\AZ\times\BZ$ with marginals $\mu$ and $\eta$, a
\term{joining} of the two sources in the sense of ergodic theory \cite{Gla03}. Conversely, by
disintegration, every joining arises from a stationary channel, unique up to $\mu$-null sets. So the
morphisms from $(\AZ,\mu)$ to $(\BZ,\eta)$ in the equivariant version of the category $\Krn$ of
\cref{ch:martingales} are the joinings, composition is the relatively independent joining over the middle
factor, and the dagger reverses a joining. The reverse of $\nu$ with respect to $\mu$ is the \term{backward
channel} $\nu^\dagger\colon\BZ\to\AZ$, which gives the conditional law of the input given the output.

The rate is symmetric, $R(\mu,\nu)=R(\eta,\nu^\dagger)$. The two conditional entropy rates are the noise
$H(\omega)-H(\mu)$ of the channel and the \term{equivocation} $H(\omega)-H(\eta)=H(\mu)-R(\mu,\nu)$, which is the noise of
the backward channel. Shannon's second theorem, in Khinchin's formulation, is a statement about the
equivocation.

\section*{Notes}

Khinchin's definitions and the two theorems on the compound source are \cite[Ch.~III]{Khi56}. The
insufficiency of his finite-memory condition and its repair are discussed in \cite{Tak58,Fei59,Bre60};
ergodic properties of channels with infinite memory are treated by Adler \cite{Adl61}, and the modern theory
is in Gray's book \cite{Gra11}, where the compound source is called the hookup. The equality of ergodic and
stationary capacity is due to Parthasarathy \cite{Par61} and Breiman \cite{Bre60}; see also
\cite{Ned57,Jac59}. For joinings see \cite{Gla03}.

\section*{Exercises}

\begin{exercise}
Derive the capacities of the erasure channel and the Z-channel in \cref{ex:channels}.
\end{exercise}

\begin{exercise}
Show that the composite of binary symmetric channels with flip probabilities $\delta_1,\delta_2$ is binary symmetric
with flip probability $\delta_1(1-\delta_2)+\delta_2(1-\delta_1)$. Compute the capacity for $\delta_1=\delta_2=0.1$ and compare with
\cref{prop:capacity}(ii).
\end{exercise}

\begin{exercise}
For the channel of \cref{ex:gap} and any stationary source, compute $H(\eta)$, $H(\omega)$ and $R(\mu,\nu)$.
\end{exercise}

\begin{exercise}\label{exer:sumchannel}
Prove \cref{prop:capacity}(iii) in full, and show that $C(W\oplus W')=\log\bigl(2^{C(W)}+2^{C(W')}\bigr)$ for the channel
$W\oplus W'$ whose input and output alphabets are the disjoint unions.
\end{exercise}

\begin{exercise}
Show that the deterministic natural families $A^n\to B^n$ are the causal functions
$y_n=f_n(x_1,\dots,x_n)$, and that the kernel $y_n=x_{n+1}$ on one-sided sequences is not induced by a natural
family.
\end{exercise}
%% ---- end ch/09-channels.tex ----
%% ---- begin ch/10-feinstein.tex ----
\chapter{Feinstein's Lemma}\label{ch:feinstein}

Shannon's proof of his theorem for noisy channels chose codewords at random and averaged. Feinstein gave
the first proof that was accepted as rigorous, by a different route: he showed directly that a channel
admits many input words whose output distributions are almost disjointly supported. Khinchin calls this
Feinstein's fundamental lemma, proves it for stationary channels with finite memory, and derives Shannon's
theorems from it. This chapter proves the lemma in its modern one-shot form, which takes a page, recovers
Khinchin's version from it with McMillan's theorem, and then reads the statement as one about
retractions.

\section{Codes}

\begin{definition}\label{def:code}
Let $W\colon X\to Y$ be a morphism of $\FinStoch$ and $0\le\varepsilon<1$. An \term{$(M,\varepsilon)$-code} for $W$
consists of codewords $x_1,\dots,x_M\in X$ and pairwise disjoint decoding sets $D_1,\dots,D_M\subseteq Y$ with
\[ W(D_j\st x_j)\ge1-\varepsilon\qquad\text{for all }j. \]
$M^*(W,\varepsilon)$ is the largest $M$ for which one exists.
\end{definition}

Khinchin calls the codewords a \emph{distinguishable group} of sequences. Note that the requirement is on
each codeword separately; this is the maximal-error criterion, and it does not refer to any distribution on
messages.

Fix a distribution $P$ on $X$ and let $Q=W\circ P$ be the output distribution. The \term{information density}
is
\[ i(x;y)=\log\frac{W(y\st x)}{Q(y)}, \]
a random variable on $X\times Y$ under the joint law $P\rtimes W$, with mean $I(P,W)$.

\section{The one-shot lemma}

\begin{theorem}[Feinstein]\label{thm:feinstein}
\Scl[\cite{Fei54}; in this form see \cite{VH94,PW25}] For every distribution $P$ on $X$, every integer $M\ge1$ and
every $\gamma>0$, there is an $(M,\varepsilon)$-code for $W$ with
\[ \varepsilon=\Prob\bigl[i(X;Y)\le\log M+\gamma\bigr]+2^{-\gamma}, \]
provided this number is less than $1$.
\end{theorem}

\begin{proof}
For $x\in X$ let $E_x=\{y:i(x;y)>\log M+\gamma\}$, the set where $W(y\st x)>M2^\gamma Q(y)$. Summing this inequality
over $E_x$ gives
\begin{equation}\label{eq:QE}
 Q(E_x)\le\frac{2^{-\gamma}}{M}.
\end{equation}
Choose codewords one at a time. Given $x_1,\dots,x_k$ and $D_1,\dots,D_k$, pick any $x_{k+1}$ with
\[ W\bigl(E_{x_{k+1}}\setminus(D_1\cup\dots\cup D_k)\,\big|\,x_{k+1}\bigr)\ge1-\varepsilon \]
and let $D_{k+1}=E_{x_{k+1}}\setminus(D_1\cup\dots\cup D_k)$. Each new set is nonempty and disjoint from the earlier
ones, so the procedure stops, say after $N$ steps, with an $(N,\varepsilon)$-code. Let $D$ be the union of its
decoding sets.

At that point every $x\in X$ satisfies $W(E_x\setminus D\st x)<1-\varepsilon$. Averaging over $P$,
\[ \Prob\bigl[i(X;Y)>\log M+\gamma,\ Y\notin D\bigr]<1-\varepsilon, \]
and therefore, by \eqref{eq:QE} applied to each codeword,
\[ \Prob\bigl[i(X;Y)>\log M+\gamma\bigr]<1-\varepsilon+Q(D)\le1-\varepsilon+\frac NM\,2^{-\gamma}. \]
Rearranged, $\varepsilon<\Prob[i\le\log M+\gamma]+\frac NM2^{-\gamma}$. Comparing with the definition of $\varepsilon$ gives $N>M$.
Keep the first $M$ codewords.
\end{proof}

The proof is a greedy construction and one counting estimate. The estimate \eqref{eq:QE} says that a
decoding set on which the likelihood ratio is large has small probability under the output distribution,
so that many of them fit. The construction uses nothing about the structure of $X$, $Y$ or $W$.

\section{Memoryless channels}

\begin{theorem}\label{thm:feinsteindmc}
\Scl[\cite{Fei54}] Let $W$ be a stochastic matrix with capacity $C$. For all $\delta,\varepsilon>0$ and all
large $n$ there is a $(2^{\lceil n(C-\delta)\rceil},\varepsilon)$-code for $W^{\otimes n}$.
\end{theorem}

\begin{proof}
Let $p$ attain the capacity and take $P=p^{\otimes n}$. The information density of $n$ uses is a sum of $n$
independent copies of the one-letter density, with mean $C$. By the weak law of large numbers
$\Prob[\frac1ni\le C-\frac\delta2]\to0$. Apply \cref{thm:feinstein} with $\log M=\lceil n(C-\delta)\rceil$ and
$\gamma=n\delta/2-1$.
\end{proof}

\begin{example}\label{ex:feinsteinbsc}
For the binary symmetric channel with flip probability $0.11$ the capacity is $0.500$. With uniform inputs,
rate $0.25$ and $\gamma=n/8$, the error guaranteed by \cref{thm:feinstein} is $0.032$ at $n=200$,
$3\times10^{-5}$ at $n=1000$, and $2\times10^{-19}$ at $n=5000$. At short lengths the bound is weak
(\cref{exer:hamming}).
\end{example}

\section{Channels with memory}

Let $\nu$ be a stationary channel without anticipation and of finite memory $m$. Then the law of the output
block $y_1\dots y_n$ depends only on the input letters $x_{1-m},\dots,x_n$, and this defines a morphism
\[ W_n\colon A^{n+m}\longrightarrow B^n \]
of $\FinStoch$. The first $m$ input letters serve to put the channel into a known condition.

\begin{theorem}[Feinstein's fundamental lemma]\label{thm:feinsteinmem}
\Scl[\cite{Khi56}, Ch.~IV; with the hypotheses of \cref{thm:ergodicchannel}] Let $\nu$ be stationary, without
anticipation, of finite memory $m$ and of finite output memory, with ergodic capacity $C$. For all
$\delta,\varepsilon>0$ and all large $n$ there is a $(2^{\lceil n(C-\delta)\rceil},\varepsilon)$-code for $W_n$.
\end{theorem}

\begin{proof}
Choose an ergodic source $\mu$ with $R(\mu,\nu)>C-\delta/4$ and let $P$ be its block law on $A^{n+m}$. The
information density of $W_n$ is
\[ i_n=-\log\mu(x_{1-m}\dots x_n)-\log\eta(y_1\dots y_n)+\log\omega(x_{1-m}\dots x_n,\,y_1\dots y_n). \]
The sources $\mu$, $\eta$ and $\omega$ are ergodic by \cref{thm:ergodicchannel}, so by \cref{thm:mcmillan} the three
terms divided by $n$ converge in probability to $H(\mu)$, $H(\eta)$ and $-H(\omega)$; the $m$ extra letters do not
affect the limits. Hence $\frac1ni_n\to R(\mu,\nu)$ in probability, and \cref{thm:feinstein} applies as in the
memoryless case.
\end{proof}

This is the one place in the whole development where the ergodicity of the compound source is needed, and
it is the reason the gap discussed in \cref{ch:channels} matters. Khinchin's own proof does not pass
through a one-shot statement. It builds the distinguishable sequences directly inside the typical sets
supplied by McMillan's theorem, using the inequalities of \cref{lem:partial,lem:feinstein3}, and takes ten
pages. The idea is the same.

The proof shows what is really required of the channel and the source: that the normalized information
density converge in probability. A pair with this property is called \term{information stable}, after
Dobrushin \cite{Dob59}. For an arbitrary sequence of channels $W_n$ the capacity is the supremum, over input
processes, of the largest number that the normalized information density exceeds with probability tending
to one \cite{VH94}; stationarity, ergodicity and memory conditions are sufficient conditions for this
number to be a limit of mutual informations.

\section{Codes as retractions}

A code is a pair of maps $e\colon[M]\to X$ and $d\colon Y\to[M]$: $e$ lists the codewords, and $d$ sends $D_j$ to
$j$. The condition of \cref{def:code} says that every diagonal entry of the stochastic matrix
\[ [M]\xrightarrow{\ e\ }X\xrightarrow{\ W\ }Y\xrightarrow{\ d\ }[M] \]
is at least $1-\varepsilon$. For $\varepsilon=0$ this says $d\circ W\circ e=\id$: the identity of $[M]$ is a retract of
$W$. In general the composite is within $\varepsilon$ of the identity, in the total variation distance of
\cref{thm:enriched}, uniformly over inputs.

\begin{definition}
The \term{$\varepsilon$-rank} of $W$ is $M^*(W,\varepsilon)$, the size of the largest finite set whose identity is an
$\varepsilon$-retract of $W$.
\end{definition}

\begin{theorem}[Capacity is the asymptotic $\varepsilon$-rank]\label{thm:rank}
\Scl[\cite{Fei54,Wol57}] For a stochastic matrix $W$ and every $\varepsilon\in(0,1)$,
\[ \lim_{n\to\infty}\frac1n\log M^*(W^{\otimes n},\varepsilon)=C(W). \]
\end{theorem}

\begin{proof}
The lower bound is \cref{thm:feinsteindmc}. For the upper bound in the limit $\varepsilon\to0$, let the message
$J$ be uniform on $[M]$, sent as $e(J)$ and decoded as $\hat J$. The probability of error is at most
$\varepsilon$, so by Fano's inequality (\cref{lem:feinstein3}) and data processing,
\[ \log M=I(J;\hat J)+H(J\st\hat J)\le I(X^n;Y^n)+1+\varepsilon\log M\le nC+1+\varepsilon\log M. \]
Thus $\frac1n\log M^*(W^{\otimes n},\varepsilon)\le(C+\frac1n)/(1-\varepsilon)$. That the limit is $C$ for every fixed
$\varepsilon<1$, and not merely as $\varepsilon\to0$, is Wolfowitz's strong converse.
\end{proof}

Set this beside \cref{prop:corank}. For an ergodic source $\mu$ and a memoryless channel $W$,
\begin{align*}
 H(\mu)&=\lim_n\tfrac1n\log\min\{M:\ (A^n,\mu_n)\text{ is an $\varepsilon$-retract of }[M]\},\\
 C(W)&=\lim_n\tfrac1n\log\max\{M:\ [M]\text{ is an $\varepsilon$-retract of }W^{\otimes n}\},
\end{align*}
and neither limit depends on $\varepsilon\in(0,1)$. Entropy is how large a set is needed to hold the source;
capacity is how large a set the channel can hold. Both are defined by the structure of an enriched
monoidal category alone: tensor powers, composition, and the distance to an identity.

For a linear map the largest identity that is a retract of it and the smallest identity through which it
factors have the same dimension, the rank. For stochastic matrices the two exact notions are different
and neither is well behaved under tensor product; the first is the zero-error capacity of \cref{ch:rates}.
The tolerance $\varepsilon$, together with the passage to the limit, is what produces a single additive
invariant.

\section{What the lemma is}

It should be said plainly what the categorical language has and has not done here. It has given the
statement a form, a retraction up to $\varepsilon$, in which it composes with other statements of the same
form; the next chapter uses this. It has not shortened the proof of \cref{thm:feinstein}, which is a
counting argument about sets, and it does not construct the code, which is found by exhaustive search.
Feinstein's lemma and McMillan's theorem are the two places where the theory touches the particular, and
only the second has so far been dissolved into general statements.

\section*{Notes}

Feinstein's lemma is \cite{Fei54}; his book \cite{Fei58} and Khinchin's Chapter~IV \cite{Khi56} extend it to
channels with memory. The one-shot form with the information density is from the information-spectrum
literature \cite{VH94,Han03}; see \cite{PW25} for a textbook treatment and for comparison with the
random-coding bounds. The strong converse is due to Wolfowitz \cite{Wol57,Wol78}. Information stability was
introduced by Dobrushin \cite{Dob59}.

\section*{Exercises}

\begin{exercise}
Prove \eqref{eq:QE}.
\end{exercise}

\begin{exercise}\label{exer:hamming}
For the binary symmetric channel with flip probability $\delta$ and uniform inputs on $\{0,1\}^n$, show that
$i(x;y)=n+d\log\delta+(n-d)\log(1-\delta)$ with $d$ the Hamming distance, so that the sets $E_x$ are Hamming
balls. For $n=7$, $\delta=0.01$ and $M=16$, find the best error guaranteed by \cref{thm:feinstein} and compare
it with the error probability of the $(7,4)$ Hamming code.
\end{exercise}

\begin{exercise}
Compute $M^*(W,\varepsilon)$ for the identity channel on a set of $k$ elements and for a channel that ignores
its input, for all $\varepsilon\in[0,1)$.
\end{exercise}

\begin{exercise}
Show that allowing a stochastic encoder $e\colon[M]\to X$ in \cref{def:code} does not increase
$M^*(W,\varepsilon)$. Give an example in which a stochastic decoder achieves a smaller maximal error than
every deterministic decoder for the same codewords.
\end{exercise}

\begin{exercise}
Let $W$ be the binary erasure channel with erasure probability $e$. Show that a set of $M$ distinct
codewords of length $n$, decoded by returning the unique codeword consistent with the unerased positions
when there is one, has maximal error at most $\varepsilon$ provided every codeword is, with probability
$1-\varepsilon$, distinguished from all others by the unerased positions. Deduce that linear codes of rate
below $1-e$ exist with small error, by counting.
\end{exercise}
%% ---- end ch/10-feinstein.tex ----
%% ---- begin ch/11-shannon.tex ----
\chapter{Shannon's Theorems}\label{ch:shannon}

Everything is now in place. McMillan's theorem makes a long block from an ergodic source an approximate
retract of a set of $2^{nH}$ points. Feinstein's lemma makes a set of $2^{nC}$ points an approximate retract of
a long block of channel uses. If $H<C$ the first set fits inside the second, and the composite of the two
retractions transmits the source through the channel. This is Shannon's theorem as Khinchin proves it in
his last chapter. We present it in that form, add the converse, which Khinchin does not treat, and observe
that the two halves of the theorem are of different kinds. The chapter ends with polar codes, where the
martingale of \cref{ch:martingales} returns in a new role.

\section{Coding without noise}

A \term{prefix code} for a finite set $X$ is an injective map $c$ from $X$ to finite binary strings such that
no codeword is an initial segment of another. Write $\ell(x)$ for the length of $c(x)$.

\begin{theorem}[Kraft's inequality and the noiseless coding theorem]\label{thm:noiseless}
\Scl[\cite{Kra49,Sha48}] The lengths of a prefix code satisfy $\sum_x2^{-\ell(x)}\le1$, and every assignment of
lengths satisfying this inequality is realized by a prefix code. For a distribution $p$ on $X$ the least
expected length $L^*(p)$ of a prefix code satisfies
\[ H(p)\le L^*(p)<H(p)+1. \]
\end{theorem}

\begin{proof}
A codeword of length $\ell$ determines a cylinder of measure $2^{-\ell}$ in the space of infinite binary
sequences with the fair coin measure, and the prefix condition says that the cylinders are disjoint. For
the lower bound let $K=\sum_x2^{-\ell(x)}\le1$ and $q(x)=2^{-\ell(x)}/K$; then
$\sum_xp(x)\ell(x)-H(p)=\KL pq-\log K\ge0$ by \cref{prop:gibbs}. For the upper bound take
$\ell(x)=\lceil-\log p(x)\rceil$.
\end{proof}

Applied to blocks of length $n$ from a stationary source, the theorem gives codes whose expected length
per letter lies between $H_n/n$ and $H_n/n+1/n$, and both tend to $H(\mu)$. So for codes of variable length
judged by their expected length the entropy of the source is the optimal rate, for every stationary
source. Ergodicity is needed for the stronger statement that the length is close to $nH$ with high
probability, which is the form in which Khinchin states the result (his Theorem~4) and the form needed for
transmission over a channel.

\begin{example}\label{ex:huffman}
For $p=(0.7,0.2,0.1)$, $H(p)\approx1.157$. The optimal prefix code for single letters has expected length $1.3$.
For blocks of $2$, $3$, $4$ and $6$ letters the optimal expected lengths per letter are $1.165$, $1.175$,
$1.164$ and $1.162$. The convergence to $H$ is not monotone.
\end{example}

The proof identifies an optimal code with an embedding of the source into the fair-coin source: the
encoded stream is, as nearly as integer lengths allow, a sequence of independent fair bits. In
\cref{ch:rates} this becomes a theorem of ergodic theory.

\section{Codes and channels}

Khinchin defines a code as a map $\theta\mapsto x(\theta)$ from sequences over a source alphabet $A_0$ to sequences
over the channel alphabet $A$, and remarks that it can be regarded as a channel $[A_0,\rho,A]$ without noise.
Connecting the source to the code and the code to the channel is the composite
\[ 1\xrightarrow{\ \mu\ }A_0^{\Z}\xrightarrow{\ \rho\ }\AZ\xrightarrow{\ \nu\ }\BZ \]
of \cref{ch:channels}. The codes he uses are block codes, which map each block of $n$ source letters to a
block of $n+m$ channel letters, where $m$ is the memory of the channel. Such a map commutes with the
appropriate powers of the two shifts, not with the shifts themselves, and the sources it produces are
stationary only for the block shift. This is harmless; one either works with the block shift throughout,
as Khinchin does, or averages over the phase.

\section{The first theorem}

\begin{lemma}[Retractions compose]\label{lem:compose}
\Sob Let $(e_s,d_s)$ be an $(M,\varepsilon_1)$-compression of a finite probability space $(X,p)$ in the sense of
\cref{def:compression}, and $(e_c,d_c)$ an $(M,\varepsilon_2)$-code for $W\colon U\to V$ in the sense of
\cref{def:code}. Then for $x$ drawn from $p$, sent as $e_c(e_s(x))$ through $W$ and decoded by
$d_s\circ d_c$, the result equals $x$ with probability at least $1-\varepsilon_1-\varepsilon_2$.
\end{lemma}

\begin{proof}
With probability at least $1-\varepsilon_1$ the point $x$ satisfies $d_s(e_s(x))=x$. Whatever the message
$j=e_s(x)$ is, the channel code returns it with probability at least $1-\varepsilon_2$.
\end{proof}

The second step is where the maximal-error criterion of \cref{def:code} is used. The compression may
concentrate the source on a few messages, and the channel code must work for each of them. A code that is
good only on average over messages would not compose with an arbitrary source (\cref{exer:average}). This is
why Feinstein's formulation suits Khinchin's proof.

\begin{figure}[ht]\centering
\begin{tikzpicture}[x=0.95cm,y=1cm]
  \node[ogbox] (mu) at (0,0) {$\mu_n$};
  \node[ogbox] (es) at (1.9,0) {$e_s$};
  \node[ogbox] (ec) at (4.1,0) {$e_c$};
  \node[ogbox] (W) at (6.7,0) {$W_n$};
  \node[ogbox] (dc) at (9.1,0) {$d_c$};
  \node[ogbox] (ds) at (11.3,0) {$d_s$};
  \draw[fw] (mu) -- (es);
  \draw[fw] (es) -- node[above=2pt,lab,black]{$[M]$} (ec);
  \draw[fw] (ec) -- node[above=2pt,lab,black]{$A^{n+m}$} (W);
  \draw[fw] (W) -- node[above=2pt,lab,black]{$B^n$} (dc);
  \draw[fw] (dc) -- node[above=2pt,lab,black]{$[M]$} (ds);
  \draw[fw] (ds) -- node[above=2pt,lab,black]{$A_0^n$} (12.9,0);
\end{tikzpicture}
\caption{Shannon's first theorem as a composite of two approximate retractions. The middle three boxes are
within $\varepsilon$ of the identity of $[M]$ by Feinstein's lemma; the outer two are within $\varepsilon$ of the
identity on $\mu_n$-typical blocks by McMillan's theorem.}\label{fig:shannon}
\end{figure}

\begin{theorem}[Shannon's first theorem]\label{thm:shannon1}
\Scl[\cite{Sha48,Fei54,Khi56}] Let $\nu$ be a channel as in \cref{thm:feinsteinmem}, with ergodic capacity $C$, and let
$[A_0,\mu]$ be an ergodic source with entropy $H_0<C$. For every $\varepsilon>0$ and all large $n$ there are maps
$A_0^n\to A^{n+m}$ and $B^n\to A_0^n$ such that a block of $n$ letters from the source, encoded, transmitted and
decoded, is recovered with probability at least $1-\varepsilon$.
\end{theorem}

\begin{proof}
Choose $\delta>0$ with $H_0+\delta<C-\delta$ and put $M=2^{\lceil n(H_0+\delta)\rceil}$. By \cref{prop:corank} the block
law $\mu_n$ has an $(M,\varepsilon/2)$-compression for large $n$. By \cref{thm:feinsteinmem} the block channel $W_n$
has a $(2^{\lceil n(C-\delta)\rceil},\varepsilon/2)$-code for large $n$, and $2^{\lceil n(C-\delta)\rceil}\ge M$. Apply
\cref{lem:compose}.
\end{proof}

\section{The second theorem}

Khinchin's second theorem says that the code can be chosen so that the rate of transmission between the
source and the received signal is as close as desired to the entropy $H_0$ of the source, or equivalently
so that the equivocation per letter is small.

\begin{theorem}[Shannon's second theorem]\label{thm:shannon2}
\Scl[\cite{Khi56}, \S16] Under the hypotheses of \cref{thm:shannon1}, for every $\varepsilon'>0$ there is a code for
which the equivocation of the source block given the received block is less than $n\varepsilon'$.
\end{theorem}

\begin{proof}
Take the code of \cref{thm:shannon1}. The received block determines the decoded block, which differs from
the source block with probability at most $\varepsilon$. By Fano's inequality (\cref{lem:feinstein3})
the equivocation is at most $1+\varepsilon\,n\log|A_0|$.
\end{proof}

In the language of \cref{ch:inequalities}: a morphism within $\varepsilon$ of having a left inverse has
equivocation at most $\hb(\varepsilon)+\varepsilon\log(\text{size})$. The second theorem is the first theorem passed
through Fano's inequality, and Khinchin proves it that way.

\section{The converse, and the two kinds of statement}

\begin{theorem}[Converse]\label{thm:converse}
\Scl[\cite{Fan61}] Let $W$ be a memoryless channel with capacity $C$ and $\mu$ a stationary source with entropy
$H_0>C$. For every $n$ and every pair of maps $A_0^n\to A^n$, $B^n\to A_0^n$ the probability $P_e$ that a block is
not recovered satisfies
\[ P_e\ \ge\ \frac{H_0-C-1/n}{\log|A_0|}. \]
\end{theorem}

\begin{proof}
Let $\theta$ be the source block and $\hat\theta$ the decoded block. Then
$nH_0\le H(\theta)=I(\theta;\hat\theta)+H(\theta\st\hat\theta)\le nC+1+P_e\,n\log|A_0|$, by data processing, \cref{thm:dmc}
and Fano's inequality.
\end{proof}

Compare the ingredients. The converse uses the chain rule, the data-processing inequality, the
additivity of capacity over independent uses, and Fano's inequality. Each of these is a property of a
function on morphisms: functoriality, monotonicity under composition, additivity under tensor, continuity
at identities. The direct theorem uses McMillan's theorem and Feinstein's lemma, which assert that certain
morphisms exist. The first kind of statement is what category theory handles well, and the converse can be
stated for any function with those properties.

\begin{theorem}[A universal property of capacity]\label{thm:universal}
\Sob Let $\Phi$ assign a number in $[0,\infty)$ to each morphism of $\FinStoch$ so that
\begin{enumerate}[label=(\roman*)]
\item $\Phi(g\circ f)\le\min\{\Phi(f),\Phi(g)\}$;
\item $\Phi(f\otimes g)\le\Phi(f)+\Phi(g)$;
\item if $f\colon[M]\to[M]$ has all diagonal entries at least $1-\varepsilon$, then
$\Phi(f)\ge(1-\varepsilon)\log M-1$.
\end{enumerate}
Then $\frac1n\log M^*(W^{\otimes n},\varepsilon)\le(\Phi(W)+\frac1n)/(1-\varepsilon)$ for all $W$, $n$ and $\varepsilon$.
Capacity satisfies \textup{(i)--(iii)}, and it is the least function that does: $\Phi\ge C$ for every such
$\Phi$.
\end{theorem}

\begin{proof}
If $(e,d)$ is an $(M,\varepsilon)$-code for $W^{\otimes n}$ then by (iii), (i) and (ii),
$(1-\varepsilon)\log M-1\le\Phi(d\circ W^{\otimes n}\circ e)\le\Phi(W^{\otimes n})\le n\Phi(W)$. Capacity satisfies (i) and
(ii) by \cref{prop:capacity}, and (iii) by Fano's inequality with a uniform input. Finally, by
\cref{thm:rank} the left side of the displayed bound tends to $C(W)$, so $C(W)\le\Phi(W)/(1-\varepsilon)$ for
every $\varepsilon$.
\end{proof}

The first half of the theorem, the bound, is the converse and is formal. The second half, minimality, is
the coding theorem: it says that no obstruction of this general kind is sharper than mutual information,
and it rests on Feinstein's lemma. Stated this way Shannon's theorem is the assertion that a certain
extremal problem over monotone functions has the explicit solution $\max_pI(p,W)$.

\section{Separation}

In \cref{fig:shannon} the composite factors through the finite set $[M]$. The source is first turned into
one of $M$ messages without reference to the channel, and the channel is used to send one of $M$ messages
without reference to the source. \Cref{thm:shannon1,thm:converse} together say that for an ergodic source and
a memoryless channel nothing is lost, in the limit, by insisting on this factorization. That is the
source--channel separation theorem. It is a statement about limits and about stable systems. For
non-ergodic sources or channels, where the information density does not concentrate, separation can fail
\cite{VVS95}, and in networks with several senders and receivers it fails in general.

\section{Polarization: the martingale returns}

Feinstein's lemma finds a code by search. For a large class of channels there is an explicit construction,
due to Ar\i kan, whose analysis is a martingale argument.

Let $W\colon\{0,1\}\to Y$ be a channel with binary input and write $I(W)$ for its mutual information with
uniform input. Take two independent uses of $W$ and feed them $x_1=u_1\oplus u_2$ and $x_2=u_2$, where $u_1,u_2$ are
independent uniform bits. This defines two new binary-input channels:
\[ W^-\colon u_1\mapsto(y_1,y_2),\qquad W^+\colon u_2\mapsto(y_1,y_2,u_1). \]
The first sees $u_1$ through noise and through the unknown $u_2$; the second sees $u_2$ twice, given $u_1$.

\begin{proposition}\label{prop:polar}
\Sli[\cite{Ari09}] $I(W^-)+I(W^+)=2I(W)$ and $I(W^-)\le I(W)\le I(W^+)$, with equality iff $I(W)\in\{0,1\}$.
\end{proposition}

\begin{proof}[Proof of the first statement]
The map $(u_1,u_2)\mapsto(x_1,x_2)$ is a bijection preserving the uniform distribution, so
$I(u_1u_2;y_1y_2)=2I(W)$. By the chain rule this is $I(u_1;y_1y_2)+I(u_2;y_1y_2\st u_1)$, and the second term is
$I(u_2;y_1y_2u_1)$ because $u_1$ and $u_2$ are independent.
\end{proof}

Iterating the construction $n$ times produces $2^n$ channels $W^b$, indexed by sign sequences
$b\in\{-,+\}^n$, from $2^n$ independent uses of $W$. Choose the signs by fair coin tosses and let
$I_n=I(W^{b_1\dots b_n})$. By \cref{prop:polar}, $(I_n)$ is a martingale with values in $[0,1]$.

\begin{theorem}[Ar\i kan]\label{thm:polar}
\Sli[\cite{Ari09}] For every $\delta>0$, as $n\to\infty$ the fraction of the $2^n$ channels $W^b$ with
$I(W^b)>1-\delta$ tends to $I(W)$, and the fraction with $I(W^b)<\delta$ tends to $1-I(W)$.
\end{theorem}

\begin{proof}
The increments of a martingale are orthogonal in $L^2$, so
$\sum_{k<n}\E(I_{k+1}-I_k)^2=\E(I_n-I_0)^2\le1$ and $\E(I_{k+1}-I_k)^2\to0$. On the other hand there is a function
$\kappa(\delta)>0$, not depending on the output alphabet, such that $I(W)-I(W^-)\ge\kappa(\delta)$ whenever
$\delta\le I(W)\le1-\delta$; this follows from Mrs.~Gerber's lemma \cite{WZ73,SSZ05}, and Ar\i kan argues instead
with the Bhattacharyya parameter. By \cref{prop:polar} both possible increments have this absolute value, so
the probability that $I_k\in[\delta,1-\delta]$ tends to zero. Since $\E I_n=I(W)$ and the middle range is
asymptotically empty for every $\delta$, the probability that $I_n>1-\delta$ tends to $I(W)$.
\end{proof}

A code is obtained by sending data bits on the indices $b$ with $I(W^b)$ near $1$, fixing the others, and
decoding the bits in order; the block error probability tends to zero at any rate below $I(W)$
\cite{Ari09,AT09}. For symmetric channels $I(W)$ is the capacity.

\begin{example}\label{ex:polar}
For the erasure channel with erasure probability $e$ both new channels are erasure channels, with
probabilities $2e-e^2$ and $e^2$. Starting from $e=\tfrac12$, the fraction of the $2^n$ channels with erasure
probability below $0.01$ is $0.234$, $0.373$, $0.441$ and $0.473$ for $n=6,10,14,18$. It tends to the capacity
$\tfrac12$. The mean erasure probability is $\tfrac12$ at every stage.
\end{example}

Three things in this construction belong to the themes of this book. The transform is a string diagram
built from copying, a deterministic isomorphism, and $W\otimes W$; its $n$-fold iterate is a tensor power of
one small diagram. The conservation law is the chain rule along an isomorphism, that is, functoriality. And
the proof of polarization needs only the orthogonality of the increments of a martingale, which is the
statement that the projections of \cref{ch:martingales} are orthogonal projections. The result is an explicit
$\varepsilon$-retraction of $W^{\otimes N}$ onto a set of about $2^{NI(W)}$ points. Khinchin brought the martingale
into information theory to handle the source. Half a century later it turned out to construct the code.

\section*{Notes}

Shannon's theorems are in \cite{Sha48}. Khinchin's proofs are \cite[Ch.~V]{Khi56}; his first paper treats
noiseless coding \cite[\S5]{Khi53}. Kraft's inequality is \cite{Kra49}, extended to uniquely decodable codes
by McMillan \cite{McM56}; optimal codes are due to Huffman \cite{Huf52}. Fano's inequality and the converse
are in \cite{Fan61}; see \cite{CT06,CK11,PW25}. The failure of separation for non-ergodic systems is studied in
\cite{VVS95}. Polar codes are due to Ar\i kan \cite{Ari09}; the rate of polarization is in \cite{AT09}.

\section*{Exercises}

\begin{exercise}
Find an optimal prefix code for $p=(0.4,0.3,0.2,0.1)$ and compare its expected length with $H(p)$.
\end{exercise}

\begin{exercise}
Show that $L^*(p)=H(p)$ iff every $p(x)$ is a power of $\tfrac12$.
\end{exercise}

\begin{exercise}\label{exer:average}
Give an example of a channel code with small error probability on average over uniformly chosen messages,
and a compression of a source, whose composite fails with probability close to $1$. How can the code be
repaired?
\end{exercise}

\begin{exercise}
Let $r_+(W)$ be the least size of a set through which $W$ factors in $\FinStoch$. Show that
$\Phi=\log r_+$ satisfies the hypotheses of \cref{thm:universal}, state the bound it gives, and give a channel
with $\Phi(W)>C(W)$. Does $\Phi(W)=\log\min\{|X|,|Y|\}$ satisfy the hypotheses?
\end{exercise}

\begin{exercise}\label{exer:bec}
For the erasure channel prove that $W^-$ and $W^+$ are erasure channels with probabilities $2e-e^2$ and
$e^2$. Let $f(e)=\sqrt{e(1-e)}$. Show that $\tfrac12\bigl(f(2e-e^2)+f(e^2)\bigr)\le\tfrac{\sqrt3}{2}f(e)$, and deduce
\cref{thm:polar} for erasure channels without any martingale theorem.
\end{exercise}
%% ---- end ch/11-shannon.tex ----
%% ---- begin ch/12-rates.tex ----
\chapter{Rates and Spectra}\label{ch:rates}

Entropy and capacity were obtained in the last chapters as limits: growth rates of the sizes of sets that
are approximate retracts of, or admit approximate retractions onto, tensor powers. Two features of the
definitions did the work, the tolerance $\varepsilon$ and the passage to the limit. This chapter asks what
each contributes. Without the tolerance, the limits still exist but are governed by a family of invariants
and not by one number. Strassen's theory of asymptotic spectra describes such families. In the infinite
setting of ergodic theory, on the other hand, the tolerance is not needed at all. None of this is in
Khinchin; it is the context in which his theorems now sit.

\section{Coding without error}

Let $W\colon X\to Y$ be a stochastic matrix. Two inputs are \term{confusable} if some output has positive
probability under both. The \term{confusability graph} $G_W$ has vertex set $X$ and an edge between
confusable inputs. A $(M,0)$-code is a set of $M$ pairwise non-confusable inputs, so
$M^*(W,0)=\alpha(G_W)$, the independence number, and for $n$ uses
$M^*(W^{\otimes n},0)=\alpha(G_W^{\boxtimes n})$, where $\boxtimes$ is the strong product of graphs.

\begin{definition}[Shannon]
The \term{zero-error capacity} of $W$ is $C_0(W)=\lim_n\frac1n\log\alpha(G_W^{\boxtimes n})=\log\Theta(G_W)$.
\end{definition}

\begin{example}\label{ex:pentagon}
Let $X=Y=\Z/5$ and let $W$ send $x$ to $x$ or $x+1$ with probability $\tfrac12$ each. Its capacity is
$\log5-1\approx1.322$. Its confusability graph is the pentagon $C_5$, with $\alpha(C_5)=2$, so one use carries one
bit without error. But $\alpha(C_5\boxtimes C_5)=5$: the five words $(i,2i)$ are pairwise non-confusable. So
two uses carry $\log5$ bits, and $C_0\ge\tfrac12\log5\approx1.161$.
\end{example}

\begin{theorem}\label{thm:zeroerror}
\Scl[\cite{Sha56,Lov79,Hae79,Alo98}] $\Theta(C_5)=\sqrt5$, so the bound in \cref{ex:pentagon} is the zero-error
capacity. In general $\Theta$ is not multiplicative under the strong product and not additive under
disjoint union: there are graphs with $\Theta(G\boxtimes H)>\Theta(G)\,\Theta(H)$ and with
$\Theta(G\sqcup H)>\Theta(G)+\Theta(H)$. No algorithm is known that computes $\Theta$.
\end{theorem}

Compare with \cref{prop:capacity}. Capacity is additive under tensor product, satisfies the sum formula of
\cref{exer:sumchannel}, and is the solution of a convex optimization problem. Zero-error capacity has none of these
properties. The exact rank of a stochastic matrix, in the sense of the largest identity that is a retract
of it, does not become a homomorphism even after regularization.

\section{Asymptotic spectra}

Strassen found the right framework for regularized quantities of this kind while studying the complexity of
matrix multiplication. Let $S$ be a commutative semiring containing the natural numbers, with a preorder
$\le$ compatible with addition and multiplication, restricting to the usual order on $\N$, and such that
every element is bounded by a natural number times any nonzero element. Define the \term{rank}
$R(a)=\min\{n\in\N:a\le n\}$ and the \term{subrank} $Q(a)=\max\{n\in\N:n\le a\}$, and their regularizations
$\tilde R(a)=\lim_nR(a^n)^{1/n}$ and $\tilde Q(a)=\lim_nQ(a^n)^{1/n}$. The \term{asymptotic spectrum} $\mathbf{X}(S)$ is
the set of monotone semiring homomorphisms $S\to\R_{\ge0}$.

\begin{theorem}[Strassen]\label{thm:strassen}
\Sli[\cite{Str88}] $\mathbf{X}(S)$ is a compact Hausdorff space, and for every $a\in S$,
\[ \tilde Q(a)=\min_{\phi\in\mathbf{X}(S)}\phi(a),\qquad\tilde R(a)=\max_{\phi\in\mathbf{X}(S)}\phi(a). \]
Moreover $a^n\le b^{n+o(n)}$ for large $n$ iff $\phi(a)\le\phi(b)$ for all $\phi\in\mathbf{X}(S)$.
\end{theorem}

\begin{theorem}[Zuiddam]\label{thm:zuiddam}
\Sli[\cite{Zui19}] Finite graphs, with disjoint union as sum, strong product as product, and the preorder
in which $G\le H$ when there is a homomorphism from the complement of $G$ to the complement of $H$, form
such a semiring. Its subrank is the independence number, and therefore
\[ \Theta(G)=\min_{\phi\in\mathbf{X}(\mathrm{graphs})}\phi(G). \]
The Lov\'asz theta function, the fractional clique cover number and the fractional Haemers bounds are
points of the spectrum.
\end{theorem}

So zero-error capacity is the minimum of a family of additive, multiplicative, monotone invariants, each
of which is individually as well behaved as capacity. The family is a compact space of which only some
points are known. This is the structure that the tolerance $\varepsilon$ removes.

\section{Sources: the R\'enyi family}

The same phenomenon appears on the source side, in a form that can be computed completely. Recall the
R\'enyi entropies $H_\alpha$ of \cref{ch:uniqueness}, with $H_0(p)=\log|\supp p|$ and $H_1=H$.

\begin{theorem}[Exact, exponential and constant error]\label{thm:exponent}
\Scl[\cite{CK11}] Let $p$ be a distribution on a finite set and consider compressions of $p^{\otimes n}$ in the
sense of \cref{def:compression}.
\begin{enumerate}[label=(\roman*)]
\item With no error, $M_*(p^{\otimes n},0)=|\supp p|^n$: the rate is $H_0(p)$.
\item With error at most a fixed $\varepsilon\in(0,1)$, the rate is $H_1(p)=H(p)$.
\item With error required to be at most $2^{-nr}$, a rate $R$ strictly between $H(p)$ and $H_0(p)$ is
achievable iff
\[ r\le\sup_{\rho\ge0}\rho\,\bigl(R-H_{1/(1+\rho)}(p)\bigr). \]
\end{enumerate}
\end{theorem}

As the required exponent $r$ goes from $0$ to $\infty$ the relevant order $\alpha=1/(1+\rho)$ goes from $1$
to $0$. Each $H_\alpha$ with $0\le\alpha\le1$ is additive under tensor product and monotone under mixing
(\cref{exer:schur}), so each gives an obstruction of the kind in \cref{thm:universal}; which of them is
binding depends on how small the error must be. For transformations between distributions under
majorization, which is the same as the theory of bipartite pure quantum states under local operations,
Jensen and Vrana showed that the asymptotic spectrum is exactly the family of power sums
$p\mapsto\sum_ip_i^\alpha$ with $0\le\alpha\le1$, and expressed optimal rates as infima over it
\cite{JV20}; see also \cite{Fri17,Kli07,Tur07}.

The role of the tolerance can now be stated precisely.

\begin{proposition}[Collapse]\label{prop:collapse}
\Sob Let $\mu$ be an ergodic source and $\varepsilon>0$. For all large $n$ there is a set $S\subseteq A^n$ with
$\mu_n(S)\ge1-\varepsilon$ such that the conditioned law $\mu_n|_S$ satisfies
\[ \Bigl|\frac1nH_\alpha(\mu_n|_S)-H(\mu)\Bigr|\le4\varepsilon\qquad\text{for every }\alpha\in[0,\infty]. \]
\end{proposition}

\begin{proof}
Take $S$ as in \cref{prop:uniform}. The conditioned law has all its probabilities between
$2^{-a}/|S|$ and $2^a/|S|$ with $a=n(2\varepsilon+\frac2n)$. Then
$\log|S|-a\le H_\infty\le H_\alpha\le H_0=\log|S|$, and $\frac1n\log|S|$ is within $\varepsilon+\frac1n$ of $H(\mu)$.
\end{proof}

Before conditioning, the R\'enyi rates of an ergodic source are in general all different. Discarding a
set of probability $\varepsilon$ makes them equal. McMillan's theorem is the statement that the spectrum
of a source, in the sense of this chapter, collapses to a point once sets of small probability may be
ignored, and Shannon entropy is the value at that point. The analogue for channels is \cref{thm:rank}, with
the strong converse: the many invariants of \cref{thm:zuiddam} are replaced by one.

\section{Infinite time: entropy as a rank}

In ergodic theory the objects are stationary sources, or more generally measure-preserving systems, and
the morphisms are stationary codes. Let $B(p)$ be the source of independent letters with distribution
$p$, a \term{Bernoulli shift}.

\begin{theorem}\label{thm:ornstein}
\Scl[\cite{Sin64,Orn70,Kri70}]
\begin{enumerate}[label=(\roman*)]
\item (Sinai) If $\mu$ is ergodic and $H(p)\le H(\mu)$, then $B(p)$ is a factor of $\mu$.
\item (Ornstein) $B(p)$ and $B(q)$ are isomorphic iff $H(p)=H(q)$.
\item (Krieger) If $\mu$ is ergodic and $H(\mu)<\log k$, then $\mu$ is isomorphic to a stationary source on $k$
letters.
\end{enumerate}
\end{theorem}

For instance $B(\tfrac14,\tfrac14,\tfrac14,\tfrac14)$ and $B(\tfrac12,\tfrac18,\tfrac18,\tfrac18,\tfrac18)$ both have
entropy $2$ and are isomorphic, as Meshalkin showed by an explicit code \cite{Mes59}.

Read these as statements about rank and subrank in the preorder of factor maps. By (i) and
\cref{thm:KS}, the entropy of an ergodic source is the supremum of the entropies of its Bernoulli factors:
a subrank, with Bernoulli shifts in the role of the finite sets $[M]$. By (iii) and \cref{thm:KS} again, it is
the infimum of $\log k$ over the alphabets on which the source can be represented: a rank. The two agree,
with no tolerance and no regularization. Krieger's theorem is the noiseless coding theorem in this
setting, and Sinai's theorem says that from any ergodic source one can extract fair bits at the rate of
its entropy. The finite theorems of \cref{ch:aep,ch:shannon} are approximations to these, in which the
infinite delay of a general stationary code is replaced by blocks of length $n$ and the price is the
tolerance.

\section{Channels without noise}

Shannon's 1948 paper begins with a channel that makes no errors but restricts which sequences may be sent.
If the allowed sequences are the paths in a finite directed graph with adjacency matrix $\mathsf{A}$, the
number of allowed blocks of length $n$ grows like $\lambda^n$, where $\lambda$ is the largest eigenvalue of
$\mathsf{A}$, and the capacity is $\log\lambda$.

\begin{theorem}\label{thm:parry}
\Scl[\cite{Sha48,Par64}] For an irreducible graph, $\log\lambda$ is the maximum of $H(\mu)$ over stationary
sources supported on allowed sequences, and the maximum is attained by a unique Markov source.
\end{theorem}

In dynamics $\log\lambda$ is the topological entropy of the shift of finite type and the theorem is the
variational principle for it. Here the exact count and the approximate one agree because the channel is
deterministic: with no noise, $\varepsilon$ has nothing to do.

\begin{example}\label{ex:golden}
Forbid two consecutive ones. The number of allowed blocks of length $n$ is a Fibonacci number, and the
capacity is $\log\frac{1+\sqrt5}{2}\approx0.694$. The maximizing source is the Markov chain that follows a $0$ by a
$1$ with probability $\frac{3-\sqrt5}{2}\approx0.382$ and always follows a $1$ by a $0$.
\end{example}

\section{Other entropies}

Several notions that carry the name entropy arise from categorical constructions of the same general
shape, a growth rate attached to an endomorphism. Dimitrov, Haiden, Katzarkov and Kontsevich define the
entropy of an exact endofunctor of a triangulated category as the growth rate of the complexity of the
images of a generator under its powers \cite{DHKK14}. Dikranjan and Giordano Bruno derive the topological,
measure-theoretic and algebraic entropies from a single functorial scheme \cite{DGB13}. We mention them to
mark the boundary of this book: they generalize the entropy of \cref{thm:KS}, an invariant of a
dynamical system, and not the coding theorems.

\section*{Notes}

Zero-error capacity was introduced by Shannon \cite{Sha56}; the pentagon was settled by Lov\'asz
\cite{Lov79}. Asymptotic spectra are due to Strassen \cite{Str88}, and their application to graphs to
Zuiddam \cite{Zui19}. The resource-theoretic point of view on rates is developed in \cite{CFS16,Fri17}. Error
exponents and their expression through R\'enyi entropies are treated in \cite{CK11}. For the isomorphism
theory of Bernoulli shifts see \cite{Orn70,Gla03}; for symbolic dynamics and constrained channels,
\cite{LM95}.

\section*{Exercises}

\begin{exercise}
Verify that $\alpha(C_5)=2$ and that the words $(i,2i)$, $i\in\Z/5$, are pairwise non-confusable for two uses of
the channel of \cref{ex:pentagon}. Find the capacity-achieving input and confirm $C=\log5-1$.
\end{exercise}

\begin{exercise}\label{exer:schur}
Show that if $q=Dp$ for a doubly stochastic matrix $D$ then $H_\alpha(q)\ge H_\alpha(p)$ for every $\alpha\ge0$.
Deduce that if $q^{\otimes m}=Dp^{\otimes n}$ for a doubly stochastic $D$ then $nH_\alpha(p)\le mH_\alpha(q)$ for all
$\alpha$.
\end{exercise}

\begin{exercise}
Prove \cref{thm:exponent}(i). For $p=(0.9,0.1)$ and $R=0.7$, compute the exponent in \cref{thm:exponent}(iii) and
compare it with $\KL{(1-\tau,\tau)}{p}$, where $\hb(\tau)=R$ and $0.1<\tau<\tfrac12$.
\end{exercise}

\begin{exercise}
Prove the claims of \cref{ex:golden}: count the allowed blocks, and maximize the entropy of a Markov chain on
$\{0,1\}$ with $q_{11}=0$.
\end{exercise}

\begin{exercise}
Compute the entropies of $B(\tfrac12,\tfrac12)$, $B(\tfrac13,\tfrac13,\tfrac13)$ and Meshalkin's two shifts. Which
of the four is a factor of which?
\end{exercise}
%% ---- end ch/12-rates.tex ----
\part{Assessment}
%% ---- begin ch/13-coda.tex ----
\chapter{What the Language Buys}\label{ch:coda}

Khinchin's conclusion to his second paper says that the proof he has given is long and complicated but
rests on a single idea, and he restates the idea in two pages. This chapter attempts the same for the
present book, and then says where its method stopped working.

\section{The idea}

There is one category. Its objects are sequence spaces with their shifts; its morphisms are equivariant
Markov kernels; sources are its states, channels its morphisms, codes its deterministic morphisms. It is
monoidal, its hom-sets carry a divergence for which composition is short, and, taken up to almost sure
equality, it has a dagger. Shannon's theory is the study of two numerical invariants of this category.
Entropy measures a state by the smallest finite set of which its long blocks are approximate retracts;
capacity measures a morphism by the largest finite set that is an approximate retract of its long blocks.
The coding theorem says that a state can be pushed through a morphism when the first number is smaller
than the second, because retractions compose, and cannot when it is larger, because both numbers are
monotone.

That such invariants exist, are finite, and are given by the formulas $-\sum p\log p$ and $\max I$ is the
content of the theory. The formula for entropy is forced by the chain rule, which is a cocycle condition.
The existence of the limits is McMillan's theorem and Feinstein's lemma.

\section{What became formal}

The following statements, each of which costs Khinchin a computation, came out of general principles.

\begin{center}\small
\renewcommand{\arraystretch}{1.25}
\begin{tabular}{@{}p{0.43\textwidth}p{0.49\textwidth}@{}}
\toprule
\textbf{Statement} & \textbf{Mechanism}\\\midrule
$H(AB)=H(A)+H_A(B)$ & functoriality of $H$ on $\FinProb$; the cocycle condition\\
symmetry of entropy & commutativity of the monoid of observables\\
uniqueness of entropy & $H^1(\Omega)\iso\R$, given the regularity theorem for the fundamental equation\\
Shannon's inequality and its generalizations & positivity of relative entropy and the chain rule\\
data processing & composition is short: the enrichment\\
the compound source is stationary & morphisms of $\Dyn$ compose\\
absence of anticipation & naturality between towers\\
ergodic decomposition & disintegration over the invariant quotient\\
convergence of conditional probabilities, in mean & monotone sequences of idempotents converge\\
McMillan's theorem, in mean & chain rule, two idempotent limits, one tail estimate\\
the second Shannon theorem & Fano's inequality: near-retractions lose little\\
the converse & any monotone subadditive normalized function bounds the rate\\
\bottomrule
\end{tabular}
\end{center}

\section{What did not}

Five things resisted, and they are the mathematical substance of the subject.

\emph{The regularity theorem.} \Cref{thm:H1} reduces uniqueness to the statement that measurable solutions of
the fundamental equation are multiples of the binary entropy. That statement is analysis, and without a
regularity hypothesis it is false. Cohomology organizes the theorem; it does not prove it.

\emph{Almost sure convergence.} The theorems of Doob, Birkhoff and Breiman need maximal inequalities. The
categorical convergence results currently available are in norm. For the coding theorems this is enough,
which is itself worth knowing, but the gap is real.

\emph{The tail estimate.} \Cref{lem:tail} is three lines and elementary, and the proof of McMillan's theorem
cannot do without it or something like it. It is the point at which the logarithm, which is unbounded,
meets a convergence theory built for bounded functions.

\emph{Feinstein's lemma.} The one-shot lemma is a greedy construction and a counting bound. We gave its
statement a categorical form and proved nothing about it by categorical means. The same is true of the
strong converse.

\emph{Ergodicity of the compound source.} Here the categorical formulation did something useful, in that
it made visible the difference between an equivariant map into a sequence space and an equivariant kernel,
and so located the hypothesis missing from Khinchin's theorem. But the theorem with the hypothesis restored
is proved by a mixing computation.

\section{How much of it is higher}

The title of this series promises higher categories, and the reader is owed an account. \Cref{ch:uniqueness,ch:cocycle}
use operads and the cohomology of a monoid with coefficients in a module over a presheaf of algebras; that
is homological algebra in a topos, and the deformation argument of \cref{prop:obstruction} is of the kind for
which derived language exists. Everything from \cref{ch:inequalities} on uses monoidal categories with one
layer of extra structure on the hom-sets: a divergence, a topology, or an order. These are enriched
categories and so are two-dimensional in a weak sense, but no coherence beyond dimension one was used, and
no homotopy type appeared that was not a set. The approximate retractions of \cref{ch:feinstein} suggest a
setting in which morphisms are considered up to a controlled error and composition holds up to a larger
one; we did not build it.

\section{Khinchin, seventy years on}

His definitions stand. A source is a stationary measure on a sequence space, a channel is a stationary
kernel, and the theorems are about these. Three points have changed. His finite-memory condition does not
imply what he uses it for; an independence condition on the noise must be added (\cref{ch:channels}). His
ergodic capacity is the same as the capacity defined with all stationary sources, which he left open
(\cref{thm:capacities}). And he proves no converse, so that his capacity is shown to be achievable and not
shown to be a limit; the converse is easier than anything he does prove (\cref{thm:converse}). His use of
almost sure theorems where convergence in mean suffices is a matter of economy, not of correctness.

\section{Open problems}

\begin{problem}[A synthetic McMillan theorem]
\Spg Formulate and prove the asymptotic equipartition property inside a Markov category with Kolmogorov
products, a dagger on its category of probability spaces, and enrichments in topological spaces and in
divergence spaces, from axioms satisfied by measure-theoretic probability. The proof in \cref{ch:aep}
indicates the ingredients. What is missing is a derivation of the mean ergodic theorem in the framework of
\cite{PVB24}, where the Ces\`aro averages are not a monotone net, and an account of how the two
enrichments interact, which is where \cref{lem:tail} would have to live.
\end{problem}

\begin{problem}[Maximal inequalities]
\Spg Find a categorical formulation of almost sure convergence in which the theorems of Doob and Birkhoff,
and with them the Shannon--McMillan--Breiman theorem, have proofs comparable in length to their
counterparts in mean.
\end{problem}

\begin{problem}[Higher information cohomology]
\Spg Compute $H^n(\Omega)$ for $n\ge2$ for the full structure on a finite set. Decide whether the non-Shannon
inequalities of \cref{thm:nonshannon}, which no first-order structure explains, are reflected in it.
\end{problem}

\begin{problem}[Entropy over other bases]
\Spg Entropy over $\R$ and over $\Fp$ are both the defect of additivity of a derivation
(\cref{ch:cocycle}), and both are unique solutions of the chain rule. Give a single construction, for a
suitable class of rings with a derivation-like operator, of which both are instances, and identify the
cohomology theory in which the resulting class lives. The appearance of the same functional equation in
the theory of polylogarithms \cite{Cat88,Kon95,EVG02} suggests where to look.
\end{problem}

\begin{problem}[Cohomology of processes]
\Spg Extend information cohomology to the observables of a stationary source, with the shift acting. Is the
entropy rate a class in an equivariant theory, and is its affinity (\cref{thm:affine}) a vanishing statement?
\end{problem}

\begin{problem}[The collapse of the spectrum]
\Spg Define a preordered semiring of channels in which the preorder is simulation up to a tolerance, and
prove that its asymptotic spectrum, in the sense of \cref{thm:strassen} or of a suitable extension, is the
single point $W\mapsto2^{C(W)}$. \Cref{thm:universal,prop:collapse} are evidence that such a statement holds. The
difficulty is that a preorder defined with a tolerance is not transitive without loss.
\end{problem}

\begin{problem}[Existence]
\Spg Find a structural proof of Feinstein's lemma: a general principle, valid in a class of enriched Markov
categories, that produces approximate retractions from the concentration of an information density. The
polar construction of \cref{ch:shannon} is structural but special. Is there a version of it for channels
with memory in which the martingale is indexed by the tower of \cref{prop:natural}?
\end{problem}

\begin{problem}[Ergodic morphisms]
\Spg Characterize, in terms of the invariant quotients of \cref{thm:MP}, the morphisms $\nu$ of $\Dyn$ for
which the compound source with every ergodic source is ergodic. The natural conjecture is that this holds
iff the invariant quotient of the compound system is, almost surely, that of its input; \cref{ex:gap} is a
channel for which it is strictly larger.
\end{problem}

\section*{Notes}

Khinchin's own summary is the Conclusion of \cite{Khi56}. For the programme of synthetic probability
theory in Markov categories, of which several of the problems above would be instances, see \cite{Fri20} and
the works cited in \cref{ch:ergodic,ch:martingales}, in particular the synthetic laws of large numbers of
\cite{FGLPS26}, which are the nearest existing results to the first problem.
%% ---- end ch/13-coda.tex ----
\appendix
%% ---- begin ch/A-toolkit.tex ----
\chapter{Categorical Toolkit}\label{app:toolkit}

This appendix collects the definitions used in the text. It is a reminder, not an introduction.

\section{Markov categories}

A \term{Markov category} is a symmetric monoidal category $(\CC,\otimes,1)$ in which every object $X$ carries
a commutative comonoid structure
\[ \cpy_X\colon X\to X\otimes X,\qquad\del_X\colon X\to1, \]
compatible with the tensor product, and in which $\del$ is natural: $\del_Y\circ f=\del_X$ for every $f\colon X\to Y$.
Equivalently the unit object is terminal. Morphisms $1\to X$ are called \term{states}. A morphism $f$ is
\term{deterministic} if it also commutes with copying, $\cpy_Y\circ f=(f\otimes f)\circ\cpy_X$. The deterministic
morphisms form a cartesian monoidal subcategory $\CC_{\det}$.

\begin{center}\small
\renewcommand{\arraystretch}{1.2}
\begin{tabular}{@{}lll@{}}
\toprule
\textbf{Category} & \textbf{Objects} & \textbf{Morphisms}\\\midrule
$\FinStoch$ & finite sets & stochastic matrices\\
$\BorelStoch$ & standard Borel spaces & Markov kernels\\
$\Stoch$ & measurable spaces & Markov kernels\\
$\Dyn$ & the same, with an automorphism & equivariant Markov kernels\\
\bottomrule
\end{tabular}
\end{center}

In $\FinStoch$ and $\BorelStoch$ the deterministic morphisms are the (measurable) maps; in $\Stoch$ they are the
kernels taking only the values $0$ and $1$. For a state $p$ on $X$ and a morphism $f\colon X\to Y$ the joint
state $p\rtimes f=(\id\otimes f)\circ\cpy\circ p$ on $X\otimes Y$ has marginals $p$ and $f\circ p$.

$\CC$ \term{has conditionals} if every morphism into a tensor product $X\otimes Y$ factors as its marginal on
$X$ followed by a morphism that produces $Y$ from $X$ and the input. In $\BorelStoch$ conditionals exist; this
is the existence of regular conditional probabilities. A \term{Bayesian inverse} of $f\colon X\to Y$ with
respect to a state $p$ is a morphism $f^\dagger\colon Y\to X$ with $(f\circ p)\rtimes f^\dagger$ equal to $p\rtimes f$ after
exchanging the factors. Two morphisms $f,g\colon X\to Y$ are equal \term{$p$-almost surely} if
$p\rtimes f=p\rtimes g$.

An infinite tensor product $\bigotimes_{i\in I}X_i$ is a \term{Kolmogorov product} if it is the limit of the finite
tensor products with their marginalization maps, the limit is preserved by tensoring with any object, and
the projections to finite subproducts are deterministic \cite{FR20}. In $\BorelStoch$ countable Kolmogorov
products exist and are the usual product spaces.

For a category $D$ and a Markov category $\CC$, the functors $D\to\CC_{\det}$, with natural transformations whose
components are arbitrary morphisms of $\CC$, form a Markov category \cite[\S7]{Fri20}. $\Dyn$ is the case in
which $D$ is the group $\Z$ regarded as a category with one object.

\section{Operads}

A \term{symmetric operad} $P$ in a symmetric monoidal category consists of objects $P(n)$, $n\ge0$, of
$n$-ary operations with actions of the symmetric groups, a unit in $P(1)$, and composition maps
\[ P(m)\otimes P(k_1)\otimes\dots\otimes P(k_m)\longrightarrow P(k_1+\dots+k_m) \]
that are associative, unital and equivariant. The \term{partial composite} $p\circ_iq$ inserts $q$ into the
$i$-th input of $p$ and units into the others. The operad $\Delta$ of simplices has $\Delta(n)=\Delta_n$, the
simplex of distributions on $n$ points, with the composition of \cref{ch:schemes}; it is an operad in
topological spaces. Its algebras in sets or spaces are the convex spaces.

Given an operad $P$ in an additive setting and a bimodule $M$ over it, a \term{derivation} is a family of
maps $d\colon P(n)\to M(n)$ with $d(p\circ_iq)=dp\circ_iq+p\circ_idq$. In \cref{thm:derivation} the bimodule is
$\R$ in every arity, with $p\circ_ir=p_ir$ and $r\circ_iq=r$.

\section{Cohomology of a monoid}

Let $S$ be a monoid acting on an abelian group $F$. The complex of inhomogeneous cochains has
$C^n=\{f\colon S^n\to F\}$ and coboundary
\begin{align*}
 (\delta f)(s_1,\dots,s_{n+1})={}&s_1.f(s_2,\dots,s_{n+1})+\sum_{k=1}^n(-1)^kf(\dots,s_ks_{k+1},\dots)\\
 &+(-1)^{n+1}f(s_1,\dots,s_n).
\end{align*}
Its cohomology is $\Ext^\bullet_{\Z[S]}(\Z,F)$. A 1-cocycle is a \term{crossed homomorphism},
$f(st)=f(s)+s.f(t)$, and a 1-coboundary has the form $f(s)=s.c-c$. The complex of \cref{def:complex} is the
subcomplex of local cochains for the monoid of observables acting on functions of laws by conditioning. In
the general setting of \cite{Vig20} the monoid varies over a poset and the computation is carried out for
modules over a presheaf of algebras, in the topos of presheaves on that poset.

\section{Enrichment}

A category is \term{enriched} in a monoidal category $\mathcal{V}$ when its hom-sets are objects of
$\mathcal{V}$ and composition is a morphism of $\mathcal{V}$. Three cases occur in the text.

\emph{Divergences.} A \term{divergence space} is a set $X$ with a function $D\colon X\times X\to[0,\infty]$ vanishing
on the diagonal; a morphism is a map that does not increase $D$; the tensor product is the product of sets
with the sum of the divergences. A category enriched in divergence spaces is one in which
$D(g\circ f\,\|\,g'\circ f')\le D(f\,\|\,f')+D(g\,\|\,g')$. For a Markov category one asks in addition that the tensor
product of morphisms be short \cite{Per24}. When $D$ is symmetric and satisfies the triangle inequality this
is enrichment in metric spaces in the sense of Lawvere \cite{Law73}.

\emph{Topologies.} A category is enriched in topological spaces, with the canonical closed structure, when
its hom-sets are spaces and composition is separately continuous. This is the enrichment used in
\cite{PVB24}.

\emph{Orders.} A category enriched in posets has an order on each hom-set respected by composition. The
order on idempotents in \cref{prop:idem} is of this kind.

\section{Dagger categories and idempotents}

A \term{dagger category} is a category with an involutive identity-on-objects functor
$\dagger\colon\CC^{\op}\to\CC$. A morphism $e\colon X\to X$ is a \term{dagger idempotent} if $e\circ e=e=e^\dagger$. It
\term{splits} if $e=i\circ i^\dagger$ with $i^\dagger\circ i=\id$; in $\Hilb$ the dagger idempotents are the orthogonal
projections and all of them split. Dagger idempotents on an object are partially ordered by $e\le e'$ iff
$e\circ e'=e$. The category $\Krn$ of \cref{def:krn} is a dagger category under Bayesian inversion, and
$L^2\colon\Krn^{\op}\to\Hilb$ is a dagger functor.

\section{Preordered semirings}

A \term{preordered semiring} is a commutative semiring with a preorder such that $a\le b$ implies
$a+c\le b+c$ and $ac\le bc$. The conditions under which \cref{thm:strassen} holds are stated before it. The
asymptotic preorder is $a\lesssim b$ iff $a^n\le b^{n+o(n)}$; the theorem says that it is detected by the monotone
homomorphisms to the nonnegative reals.
%% ---- end ch/A-toolkit.tex ----
%% ---- begin ch/B-concordance.tex ----
\chapter{Concordance with Khinchin}\label{app:concordance}

The table lists the sections of the two papers in \cite{Khi57} and where their subject is treated here.
Section numbers are those of the Dover edition. The correspondence is by topic; no passage of the source is
reproduced.

\begin{center}\small
\renewcommand{\arraystretch}{1.22}
\begin{longtable}{@{}p{0.47\textwidth}p{0.45\textwidth}@{}}
\toprule
\textbf{Khinchin} & \textbf{This book}\\\midrule
\endhead
\multicolumn{2}{@{}l}{\emph{The Entropy Concept in Probability Theory} (1953)}\\
\S1 Entropy of finite schemes & \cref{ch:schemes}\\
\S2 The uniqueness theorem & \cref{ch:uniqueness,ch:cocycle}\\
\S3 Entropy of Markov chains & \cref{ch:sources}, \cref{prop:markov}\\
\S4 Fundamental theorems (Theorems 2, 3) & \cref{ch:aep}, \cref{thm:mcmillan,thm:counting}\\
\S5 Application to coding theory (Theorem 4) & \cref{ch:shannon}, \cref{thm:noiseless}\\[4pt]
\multicolumn{2}{@{}l}{\emph{On the Fundamental Theorems of Information Theory} (1956)}\\
Ch.~I, \S1 Two generalizations of Shannon's inequality & \cref{ch:inequalities}, \cref{lem:partial,lem:SSA}\\
Ch.~I, \S2 Three inequalities of Feinstein & \cref{lem:feinstein3}\\
Ch.~II, \S3 Source, stationarity, entropy & \cref{ch:sources}, \cref{prop:rate}\\
Ch.~II, \S4 Ergodic sources & \cref{ch:ergodic}\\
Ch.~II, \S5 The $E$ property; McMillan's theorem & \cref{ch:aep}\\
Ch.~II, \S6 Martingales; Doob's theorem & \cref{ch:martingales}\\
Ch.~II, \S7 Auxiliary propositions & \cref{lem:tail,lem:gk}\\
Ch.~II, \S8 Proof of McMillan's theorem & \cref{thm:mcmillan}\\
Ch.~III, \S9 Channel, noise, stationarity, anticipation, memory & \cref{def:channel,prop:natural}\\
Ch.~III, \S10 Connection of the channel to the source & \cref{thm:stationary}\\
Ch.~III, \S11 The ergodic case & \cref{ex:gap,thm:ergodicchannel}\\
Ch.~IV, \S\S12--13 Feinstein's fundamental lemma & \cref{ch:feinstein}, \cref{thm:feinstein,thm:feinsteinmem}\\
Ch.~V, \S14 Coding & \cref{ch:shannon}\\
Ch.~V, \S15 The first Shannon theorem & \cref{thm:shannon1}\\
Ch.~V, \S16 The second Shannon theorem & \cref{thm:shannon2}\\
Conclusion & \cref{thm:capacities}, \cref{ch:coda}\\
\bottomrule
\end{longtable}
\end{center}

\noindent Topics treated here that have no counterpart in the source: the functorial and operadic
characterizations of entropy (\cref{ch:uniqueness}); information cohomology and entropy modulo a prime
(\cref{ch:cocycle}); relative entropy and the enriched structure (\cref{ch:inequalities}); coalgebraic sources
(\cref{ch:sources}); the categorical ergodic decomposition (\cref{ch:ergodic}); the converse coding theorem and
polar codes (\cref{ch:shannon}); zero-error capacity, asymptotic spectra and the isomorphism theory of
Bernoulli shifts (\cref{ch:rates}).
%% ---- end ch/B-concordance.tex ----
%% ---- begin ch/C-computations.tex ----
\chapter{Computational Checks}\label{app:computations}

The script \texttt{verify.py} that accompanies this book recomputes every numerical example in the text
and in the solutions, and tests a number of structural claims on explicit or randomly generated finite
instances. It uses only the Python standard library, fixes its random seed, and runs in about a second;
\texttt{python3 verify.py} prints one line per check and exits with status zero if and only if all pass.
Version~1.0 performs 91 checks, all of which pass under Python~3.8 or later.

A check of this kind is evidence about the examples and about the absence of slips in the finite
statements. It is not a proof of any theorem, and the theorems tagged \textsf{classical} or
\textsf{literature} rest on the references cited for them. What the script does establish is the
following.

\begin{center}\small
\renewcommand{\arraystretch}{1.25}
\begin{longtable}{@{}p{0.09\textwidth}p{0.83\textwidth}@{}}
\toprule
\textbf{Ch.} & \textbf{What is checked}\\\midrule
\endhead
\ref{ch:schemes} & \Cref{ex:first,ex:coarse}. On random instances: $H(f)=H(p)-H(q)$ and functoriality
 (\cref{thm:functor}); the operadic chain rule; convex-linearity (\cref{prop:convexlinear}); Khinchin's
 properties; \cref{prop:lossnoise}.\\
\ref{ch:uniqueness} & The second step of Khinchin's proof on random rational distributions. Additivity,
 maximality and expansibility of the R\'enyi entropies, their limit at $\alpha=1$, and \cref{ex:renyi}. The
 Leibniz rule \eqref{eq:leibniz} for $H$ and its failure for $H_2$.\\
\ref{ch:cocycle} & On random observables and laws on a five-point space: the action axiom for
 $\alpha=1,\tfrac12,2$ (\cref{lem:action}); the cocycle condition for entropy (\cref{prop:Hcocycle});
 $\delta\delta=0$ on a generic local cochain; the Tsallis coboundary and cocycle identities and the limit
 $\alpha\to1$ (\cref{thm:tsallis,prop:obstruction}). The fundamental equation for $\hb$ and for $h(x)=x$, and,
 in a four-dimensional test space, that its solutions are spanned by $\hb$. The Leibniz rule for the Fermat
 quotient; that entropy modulo $p$ is well defined, satisfies the chain rule, equals the truncated
 logarithm and satisfies the fundamental equation, for $p=3,5,7,11,13$ (\cref{thm:modp}).\\
\ref{ch:inequalities} & On random instances: Gibbs' inequality, the chain rule and data processing; the
 three statements of \cref{thm:enriched}; \cref{prop:copy}; \cref{lem:partial}; monotonicity and submodularity
 on the lattice of partitions, with the meet computed explicitly (\cref{prop:submodular}); the three
 inequalities of \cref{lem:feinstein3}; functoriality of relative entropy on $\FinStat$.\\
\ref{ch:sources} & \Cref{ex:markov,ex:hmm}, by exact enumeration of block laws; monotonicity of the two
 bounds of \cref{thm:blackwell}; stationarity of a coalgebraic source; that a sliding block code does not
 raise block entropies; the count of equivariant maps in \cref{exer:cofreefinite}; \cref{prop:unifilar} on an
 example.\\
\ref{ch:ergodic} & \Cref{ex:mixture}, including the bound of one bit on the excess; the criterion of
 \cref{exer:cylinders} for a Markov chain and its failure for the mixture; affinity of the entropy on a
 segment of stationary Markov sources.\\
\ref{ch:martingales} & Idempotence, symmetry and the tower property for conditional expectations on finite
 spaces, and a pair that does not commute; the dyadic martingale; the likelihood-ratio martingale of
 \cref{exer:likelihood}, including the singularity of the limit; the mean ergodic theorem for a permutation;
 orthogonality of martingale increments.\\
\ref{ch:aep} & \Cref{lem:tail} for the Markov and hidden Markov sources; \cref{ex:counting,ex:mixcount}; the
 second-order prediction of \cref{exer:second}.\\
\ref{ch:channels} & Invariance of the compound source in a cyclic model (\cref{thm:stationary}); \cref{ex:gap};
 the capacities of \cref{ex:channels} by the Blahut--Arimoto iteration against the closed forms; the four
 statements of \cref{prop:capacity} and the sum formula; symmetry of the rate under the dagger; naturality of
 a memoryless family (\cref{prop:natural}); \cref{ex:isi}.\\
\ref{ch:feinstein} & The greedy construction of \cref{thm:feinstein} on 40 random channels: whenever the
 guaranteed error is below $1$ it produces at least $M$ codewords with disjoint decoding sets and that
 maximal error. The estimate \eqref{eq:QE}; the weak converse for the codes found; \cref{ex:feinsteinbsc};
 exact $\varepsilon$-ranks of small channels by exhaustive search.\\
\ref{ch:shannon} & Kraft's inequality and the bounds of \cref{thm:noiseless} for Huffman codes;
 \cref{ex:huffman}; \cref{lem:compose} on an explicit composite; \cref{prop:polar}, including the bound from
 Mrs.~Gerber's lemma, on five channels; \cref{ex:polar} and the orthogonality argument of \cref{thm:polar}.\\
\ref{ch:rates} & \Cref{ex:pentagon} by exhaustive search for independent sets, and Lov\'asz's orthonormal
 representation; monotonicity of all R\'enyi entropies under doubly stochastic maps; agreement of the two
 expressions for the exponent in \cref{thm:exponent}; \cref{prop:collapse} for independent bits at $n=2000$;
 \cref{ex:golden}; the entropies in \cref{thm:ornstein}.\\
\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,
 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.\\
\bottomrule
\end{longtable}
\end{center}

\noindent The checks on random instances use a few dozen to a few hundred instances each. They would detect
a wrong sign or a misplaced hypothesis; they say nothing about measure-theoretic statements, which are
outside the reach of a finite computation.
%% ---- end ch/C-computations.tex ----
%% ---- begin ch/D-solutions.tex ----
\chapter{Solutions to the Exercises}\label{app:solutions}

Solutions are given for every exercise, numbered as in the chapters. Where an exercise asks for a
computation, the numbers below are recomputed by the script of \cref{app:computations}.
%% ---- end ch/D-solutions.tex ----
%% ---- begin sol/01.tex ----
\section*{Chapter 1}

\sol{1.1} $g$ has image $(\tfrac34,\tfrac18,\tfrac18)$ and one nontrivial fibre, of mass $\tfrac34$ and conditional
distribution $(\tfrac23,\tfrac13)$: $H(g)=\tfrac34\hb(\tfrac23)\approx0.689$. Then $h$ has image
$(\tfrac34,\tfrac14)$ and one nontrivial fibre of mass $\tfrac14$ and conditional distribution
$(\tfrac12,\tfrac12)$: $H(h)=0.25$. The composite has $H(h\circ g)=H(p)-\hb(\tfrac14)\approx1.75-0.811=0.939$, the
sum of the two.

\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 then
$H(f)=0$ since $f$ is injective, so $H(p)=H(q)$. The converse fails: $(\tfrac12,\tfrac14,\tfrac18,\tfrac18)$
and $(a,a,b,b,b,b)$ with $2a+4b=1$ can be given the same entropy $1.75$ by the intermediate value theorem
($a=b=\tfrac16$ gives $\log6\approx2.58$ and $a\to\tfrac12$ gives $1$), and they are not isomorphic.

\sol{1.3} By \cref{prop:chainrule}, $p=(t,1-t)\circ(u_1,p')$ where $p'$ is the conditional distribution on the
other $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).

\sol{1.4} If $W=\sum_k\lambda_k\Pi_k$ with permutation matrices $\Pi_k$, concavity of $H$ gives
$H(Wp)\ge\sum_k\lambda_kH(\Pi_kp)=H(p)$. Conversely apply the hypothesis to the uniform state $u$:
$H(Wu)\ge\log|X|$ forces $Wu=u$ by \cref{prop:properties}(ii), which says that the rows of the matrix of $W$
(indexed by outputs) sum to one. Its columns sum to one because it is stochastic.

\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$ are
conditionally independent given $Y$. If both kernels are maps, $Y$ is a function of $X$ and $Z$ a function
of $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:
$H(X\st Z)=1<H(X\st Y)+H(Y\st Z)=2$.
%% ---- end sol/01.tex ----
%% ---- begin sol/02.tex ----
\section*{Chapter 2}

\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$ puts
mass $\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$, and
$H(p)=\tfrac12\cdot1+\tfrac13\log3+\tfrac16\log6\approx0.5+0.528+0.431=1.459$.

\sol{2.2} By symmetry it is enough to treat $i=n$. For $k=1$ there is nothing to prove, and $k=2$ is
recursivity. Let $q\in\Delta_k$ with $k\ge3$ and put $s=q_{k-1}+q_k$. If $s=0$ use expansibility, which is
recursivity with $q_2=0$. Otherwise let $q'=(q_1,\dots,q_{k-2},s)$. Recursivity applied to $p\circ_nq$, whose
last two entries are $p_nq_{k-1}$ and $p_nq_k$, gives
$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')$,
and recursivity for $q$ itself gives $H(q)=H(q')+sH(\tfrac{q_{k-1}}{s},\tfrac{q_k}{s})$. Combine. The full
composite $q\circ(p_1,\dots,p_m)$ is obtained by $m$ partial composites, the $i$-th of which contributes
$q_iH(p_i)$.

\sol{2.3} $\sum_{i,j}(p_iq_j)^\alpha=\sum_ip_i^\alpha\sum_jq_j^\alpha$ gives additivity. Adding a zero does not
change $\sum p_i^\alpha$. For $\alpha<1$ the function $t^\alpha$ is concave, so $\sum_ip_i^\alpha\le n^{1-\alpha}$ and
$H_\alpha\le\log n$; for $\alpha>1$ it is convex, the inequality reverses, and so does the sign of $1-\alpha$.
By 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$.

\sol{2.4} Continuity is clear. A map $f$ sends $p$ to a distribution $q$ obtained by adding entries, and
$(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$.
Then $\tfrac12f\oplus\tfrac12f'$ maps $(\tfrac14,\tfrac14,\tfrac12)$ to $(\tfrac12,\tfrac12)$ and has
$F=\log\tfrac83-1\approx0.415$, whereas $\tfrac12F(f)+\tfrac12F(f')=0.5$. In the proof, functoriality still gives
$F(f)=I(p)-I(q)$; what fails is the identity $F(f)=\sum_iq_iI(p_i)$, that is, the chain rule.

\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)$
gives $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 write
$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$ does
not change the entries at positions before $i$, so the $i$-th step adds $q_iI(p_i)$.
%% ---- end sol/02.tex ----
%% ---- begin sol/03.tex ----
\section*{Chapter 3}

\sol{3.1} As in \cref{lem:action}, the weight of the block $B\cap C$ in $Y._\alpha(Z._\alpha f)$ is
$P(B)^\alpha\bigl(P(B\cap C)/P(B)\bigr)^\alpha=P(B\cap C)^\alpha$. And $Y._\alpha1=\sum_BP(B)^\alpha$, which equals $1$ for all
$P$ and $Y$ iff $\alpha=1$.

\sol{3.2} Write $s_Y=\sum_BP(B)^\alpha$. Then
$Y._\alpha S_\alpha[Z]=\frac1{\alpha-1}\sum_BP(B)^\alpha\bigl(1-\sum_C(P(B\cap C)/P(B))^\alpha\bigr)=\frac{1}{\alpha-1}(s_Y-s_{YZ})$, and
adding $S_\alpha[Y]=\frac1{\alpha-1}(1-s_Y)$ gives $\frac1{\alpha-1}(1-s_{YZ})$. If $Y$ and $Z$ are independent,
$s_{YZ}=s_Ys_Z$ and $s=1-(\alpha-1)S_\alpha$; substitute.

\sol{3.3} The observables are $1$ and the atomic partition $X$. A 1-cochain is a pair $(f[1],f[X])$ with
$f[1]$ a constant and $f[X]$ a measurable function $h$ of $P(a)\in[0,1]$. The cocycle conditions for the four
pairs reduce to $f[1]=0$ and $X.f[X]=0$, that is, $P(a)h(1)+P(b)h(0)=0$ for all $P$. So $Z^1$ is the space of
measurable $h$ with $h(0)=h(1)=0$, there are no coboundaries, and $H^1$ is that infinite-dimensional space.

\sol{3.4} For $h(x)=x$ both sides equal $x+y$. For $\hb$, splitting off the first outcome of $(x,y,1-x-y)$
gives $\hb(x)+(1-x)\hb(\frac{y}{1-x})$ by \cref{prop:chainrule}, and splitting off the second gives the other
side. There is no contradiction, because a cocycle vanishes at deterministic laws (Step~0), which forces
$h(1)=0$.

\sol{3.5} $ab-a^pb^p=(a-a^p)\,b+a^p\,(b-b^p)$; divide by $p$ and use $a^p\equiv a$. Next
$H_5(2,4)=(1-32-1024)/5=-211\equiv4$, and $\sum_{k=1}^4 2^k/k=2+2+8\cdot3^{-1}+4$ with $3^{-1}=2$ in
$\mathbb{F}_5$, giving $9\equiv4$. In $\mathbb{F}_3$: $H_3(2,2)=(1-8-8)/3=-5\equiv1$ and
$H_3(1,1,2)=(1-1-1-8)/3=-3\equiv0$. The chain rule predicts
$H_3(2,2)+2\cdot H_3(2,2)+2\cdot H_3(1)=1+2+0\equiv0$.
%% ---- end sol/03.tex ----
%% ---- begin sol/04.tex ----
\section*{Chapter 4}

\sol{4.1} $\KL pq=\tfrac12\log2+\tfrac12\log\tfrac23\approx0.2075$ and
$\KL qp=\tfrac14\log\tfrac12+\tfrac34\log\tfrac32\approx0.1887$. The channel fixes $p$ and sends $q$ to
$(0.3,0.7)$, and $\KL{(\frac12,\frac12)}{(0.3,0.7)}=\tfrac12\log\tfrac{5}{3}+\tfrac12\log\tfrac57\approx0.1258<0.2075$.

\sol{4.2} Write $r(x,y)=p(x)r(y\st x)$ and $r'(x,y)=p'(x)r'(y\st x)$; then
$\log\frac{r}{r'}=\log\frac{p}{p'}+\log\frac{r(y\st x)}{r'(y\st x)}$, and averaging against $r$ gives the formula. In the proof
of \cref{thm:DPI} the only inequality is the positivity of
$\sum_y(f\circ p)(y)\KL{r(\,\cdot\st y)}{r'(\,\cdot\st y)}$, which vanishes iff each term with $(f\circ p)(y)>0$ does.

\sol{4.3} $\TV=1-\sum p^2=1-\tfrac38=\tfrac58$ and $\KL{\cpy\circ p}{p\otimes p}=H(p)=1.5$. Both are largest at the uniform
state, where they equal $1-\tfrac1n$ and $\log n$: the first because $\sum p^2\ge\tfrac1n$ by the
Cauchy--Schwarz inequality, the second by \cref{prop:properties}(ii).

\sol{4.4} The marginals are uniform, so $I(X;Y)=1+1-H(0.4,0.4,0.1,0.1)=2-1.722=0.278$. A function of $X$ that
is also a function of $Y$ takes the same value at $(0,0)$ and $(0,1)$, at $(0,1)$ and $(1,1)$, and so on;
all four points have positive probability, so it is constant. For the second part take $Y=X$ a fair bit:
$X\wedge Y=X$ and $I(X;Y)=H[X]=1$.

\sol{4.5} Given $Y=y$, the posterior of $X$ is $1-\varepsilon$ at $y$ and $\varepsilon/(n-1)$ elsewhere; since
$\varepsilon<1-\tfrac1n$ the maximum is at $y$, so $P_e=\varepsilon$. By the equality case of Exercise~1.3,
$H(X\st Y=y)=\hb(\varepsilon)+\varepsilon\log(n-1)$ for every $y$.
%% ---- end sol/04.tex ----
%% ---- begin sol/05.tex ----
\section*{Chapter 5}

\sol{5.1} $\pi=(b,a)/(a+b)$ and \cref{prop:markov} give the formula. It is a weighted average of $\hb(a)$ and
$\hb(b)$, so it is at most $1$, with equality iff $a=b=\tfrac12$. It equals the entropy of the marginal iff the
letters are independent, that is, iff the two rows of $Q$ agree: $a+b=1$.

\sol{5.2} An output block of length $n$ is a function of an input block of length $n+1$, so
$H_n(\phi\circ\mu)\le H_{n+1}(\mu)$; divide by $n$. For independent fair bits the outputs $x_n+x_{n+1}$ are again
independent fair bits, so both entropies are $1$. But $\phi$ is not an isomorphism: it identifies $x$ with
its complement, and complementation preserves $\mu$, so $\phi$ is two-to-one almost everywhere. Equal entropy
does not make a factor map invertible.

\sol{5.3} Given $g\colon X\to B$ put $\phi(x)_n=g(n\cdot x)$; conversely $g=\pi_0\circ\phi$. These are inverse
bijections, as in \cref{prop:cofree}. Hence there are $|B|^{|A|^N}$ equivariant maps.

\sol{5.4} Given the past, $x_{n+1}$ has distribution $e_{\tau(x_n)}$, which depends on $x_n$ only. So the letters
form a Markov chain with $q_{ab}=e_{\tau(a)}(b)$. The coalgebra is unifilar, and by \cref{prop:unifilar} its
entropy is $\sum_s\sigma(s)H(e_s)=\sum_a\pi(a)H(q_{a\,\cdot})$, where $\pi$ is the stationary distribution of the
letters and $\sigma=\tau_*\pi$. Conversely, given $Q$ take $S=A$, $\tau=\id$ and $e_a=q_{a\,\cdot}$.

\sol{5.5} Upper bound: $H(\mu)=\lim c_n$ and $c_n$ is nonincreasing (\cref{prop:rate}). Lower bound: for
every $m$,
\[ c_{n+m}\ \ge\ H(x_{n+m}\st x_0,\dots,x_{n+m-1},s_m)=H(x_{n+m}\st x_m,\dots,x_{n+m-1},s_m), \]
because given $s_m$ the letters before time $m$ are independent of those after. By stationarity the right
side is $H(x_n\st x_0,\dots,x_{n-1},s_0)$; let $m\to\infty$. Monotonicity of the lower bound: conditioning
also on $s_1$ and then discarding $x_0,s_0$, which are independent of the future given $s_1$,
$H(x_{n+1}\st x_0,\dots,x_n,s_0)\ge H(x_{n+1}\st x_1,\dots,x_n,s_1)$, and the right side is the bound for $n$.
Convergence: the gap between the bounds is $I(s_0;x_n\st x_0,\dots,x_{n-1})$, and these terms sum to at most
$H(s_0)$.
%% ---- end sol/05.tex ----
%% ---- begin sol/06.tex ----
\section*{Chapter 6}

\sol{6.1} A stationary distribution of $Q$ is a convex combination $\lambda\pi'+(1-\lambda)\pi''$ of the unique
stationary distributions of the two classes, and the corresponding Markov source is the same combination of
the two sources supported on sequences that stay in one class. Each of those is ergodic by
\cref{prop:iid}. The event of lying in the first class is invariant with measure $\lambda$, so interior
points are not ergodic. By \cref{prop:markov} the entropy is $\sum_a\pi(a)H(q_{a\,\cdot})$, which is linear in $\pi$.

\sol{6.2} If $\mu$ is ergodic, apply \cref{thm:birkhoff} to $f=1_{C'}$: $A_nf\to\mu(C')$ in $L^1$; multiply by $1_C$
and integrate. Conversely the condition extends from cylinders to all measurable sets by approximation, and
for an invariant $S$ it gives $\mu(S)=\mu(S\cap T^{-k}S)\to\mu(S)^2$.

\sol{6.3} The lower inequality is concavity of $H$ on $\Delta(A^n)$. For the upper one, let $J$ be the label of
the component: $H_n(\mu)\le H(x_1\dots x_n,J)=H(J)+H(x_1\dots x_n\st J)$. Equality holds for all $n$ when the label
is a function of every block, for instance when $\mu'$ and $\mu''$ are the two constant sequences on $\{0,1\}$:
then $H_n(\mu)=\hb(\lambda)$ and $H_n(\mu')=H_n(\mu'')=0$.

\sol{6.4} Write $\mu_n=\tfrac12\mu'_n+\tfrac12\mu''_n$. On the first component the number of ones is $0.1n+o(n)$
almost surely, so $-\frac1n\log\mu'_n(x)\to\hb(0.1)\approx0.469$ and $-\frac1n\log\mu''_n(x)=1$; the larger
probability dominates the sum and the limit is $\hb(0.1)$. On the second component the number of ones is
$\tfrac12n+o(n)$, so $-\frac1n\log\mu'_n(x)\to\tfrac12\log10+\tfrac12\log\tfrac{10}{9}\approx1.737$, and the limit is $1$.

\sol{6.5} The two sequences are exchanged by $T$, so the only invariant sets are null or conull, while
each of them is fixed by $T^2$ and is a $T^2$-invariant set of measure $\tfrac12$. Every block has one of
two values, so $H_n\le1$ and $H(\mu)=0$.
%% ---- end sol/06.tex ----
%% ---- begin sol/07.tex ----
\section*{Chapter 7}

\sol{7.1} $e_\GG(y\st x)=\tfrac12$ if $x,y\in\{1,2\}$, $\tfrac14$ if $x,y\in\{3,4,5,6\}$, and $0$ otherwise. It is
block diagonal with blocks $\tfrac12J_2$ and $\tfrac14J_4$, where $J_k$ is the all-ones matrix; these are symmetric
and idempotent. On $f(x)=x$ it gives the block averages: $1.5$ on $\{1,2\}$ and $4.5$ on $\{3,4,5,6\}$.

\sol{7.2} If $\GG\subseteq\GG'$, resampling given $\GG'$ and then given $\GG$ is resampling given $\GG$, and in the
other order the second step does not change the $\GG$-class; so both composites are $e_\GG$. Conversely if
$e_\GG e_{\GG'}=e_\GG$ then every $\GG$-measurable $g$ satisfies $\E[g\st\GG']=g$ after applying $L^2$ and taking
adjoints, so it is $\GG'$-measurable. On $\{1,2,3\}$ with the uniform distribution take the partitions
$\{1,2\}|\{3\}$ and $\{1\}|\{2,3\}$. The function $f=1_{\{1\}}$ is sent by the first projection to
$(\tfrac12,\tfrac12,0)$ and then by the second to $(\tfrac12,\tfrac14,\tfrac14)$; in the other order it is
fixed by the second and sent to $(\tfrac12,\tfrac12,0)$ by the first.

\sol{7.3} $\E[f\st\FF_n]$ is the midpoint of the dyadic interval containing $x$. On each interval $f$ minus
the midpoint is uniform on an interval of length $2^{-n}$ centred at $0$, with variance $2^{-2n}/12$.

\sol{7.4} The factors are independent with mean $\tfrac12(1.6+0.4)=1$, so $M_n$ is a martingale with mean
$1$, and $\E\sqrt{M_n}=(\tfrac12(\sqrt{1.6}+\sqrt{0.4}))^n=\rho^n$. By Markov's inequality
$\Prob(M_n>\delta)\le\rho^n/\sqrt\delta\to0$. If $M_n=\E[f\st\FF_n]$ then $M_n\to f$ in $L^1$ by \cref{cor:levy}, so $f=0$,
contradicting $\E M_n=1$.

\sol{7.5} $\sigma$ has order $6$, so $\frac16\sum_{k<6}U^k$ averages a function over the orbits of $\sigma$: it is block
diagonal with blocks $\tfrac13J_3$ and $\tfrac12J_2$. This is the conditional expectation, for the uniform
distribution, onto the $\sigma$-algebra generated by the cycles, which is the invariant $\sigma$-algebra.
%% ---- end sol/07.tex ----
%% ---- begin sol/08.tex ----
\section*{Chapter 8}

\sol{8.1} $i_n=\sum_{k<n}-\log p(x_k)$ is a sum of independent identically distributed terms with mean $H$ and
variance $\sigma^2$, so $\frac1ni_n$ has variance $\sigma^2/n$. For a bit with $\Prob(1)=p$ the term takes two values
differing by $\log\frac{1-p}{p}$, so $\sigma^2=p(1-p)\log^2\frac{1-p}{p}$; at $p=0.2$ this is $0.16\cdot4=0.64$.

\sol{8.2} By the Markov property $\mu(x_0\st x_{-k},\dots,x_{-1})=q_{x_{-1}x_0}$ for $k\ge1$. So
$i_n=g_0+\sum_{k=1}^{n-1}g_1\circ T^k$ with $g_1$ bounded on the support of $\mu$, and
$\frac1ni_n\to\E[g_1\st\II]$ in $L^1$, which is $\E g_1=H(\mu)$ if the source is ergodic.

\sol{8.3} Each block of $T_n^\varepsilon$ has probability at least $2^{-n(H+\varepsilon)}$ and the total is at most $1$;
each has probability at most $2^{-n(H-\varepsilon)}$ and the total is at least $1-\delta$. For \cref{prop:uniform}
take $S=T_n^\varepsilon$ with $n$ so large that $\mu_n(S)\ge1-\varepsilon\ge\tfrac12$. Then
$\tfrac12\,2^{n(H-\varepsilon)}\le|S|\le2^{n(H+\varepsilon)}$, and $\mu_n(C)|S|$ lies between
$\tfrac12\,2^{-2n\varepsilon}$ and $2^{2n\varepsilon}$.

\sol{8.4} Order the blocks by decreasing probability, which is by increasing number of ones. By
Exercise~6.4 the blocks with about $0.1n$ ones carry probability close to $\tfrac12$ in total and each has
probability about $\tfrac12\,2^{-n\hb(0.1)}$; there are about $2^{n\hb(0.1)}$ of them. If $\lambda<\tfrac12$ they
suffice. If $\lambda>\tfrac12$ one must add blocks from the second component, which have probability about
$\tfrac12\,2^{-n}$ each, and a fixed positive fraction of all $2^n$ blocks is needed.

\sol{8.5} The probability of a block decreases with its number of ones, so an optimal set consists of all
blocks with fewer than $k$ ones and some with exactly $k$, where $k=np+\Phi^{-1}(\lambda)\sqrt{np(1-p)}+o(\sqrt n)$ by
the central limit theorem. The number of such blocks is $2^{n\hb(k/n)+O(\log n)}$, and
$\hb(k/n)=\hb(p)+\hb'(p)(k/n-p)+O(1/n)$ with $\hb'(p)=\log\frac{1-p}{p}$. For $p=0.2$, $\sigma=0.8$; at $n=1000$ the
correction for $\lambda=0.9$ is $0.8\cdot1.2816/\sqrt{1000}\approx0.032$, predicting $0.754$ against the computed
$0.748$, and for $\lambda=0.1$ predicting $0.690$ against $0.683$. The remaining difference is the term of order
$(\log n)/n$.
%% ---- end sol/08.tex ----
%% ---- begin sol/09.tex ----
\section*{Chapter 9}

\sol{9.1} Erasure: the output reveals whether an erasure occurred, so $H(Y)=\hb(e)+(1-e)H(p)$ and
$H(Y\st X)=\hb(e)$; $I=(1-e)H(p)$, maximal at the uniform input. Z-channel: with $q=\Prob(X=1)$,
$I=\hb(q(1-\delta))-q\,\hb(\delta)$. Setting the derivative to zero, $(1-\delta)\log\frac{1-s}{s}=\hb(\delta)$ with $s=q(1-\delta)$, so
$s=1/(1+2^{\hb(\delta)/(1-\delta)})$. Substituting, $I=-\log(1-s)=\log\bigl(1+2^{-\hb(\delta)/(1-\delta)}\bigr)$, and
$2^{-\hb(\delta)/(1-\delta)}=(1-\delta)\,\delta^{\delta/(1-\delta)}$.

\sol{9.2} The output differs from the input iff exactly one of the two channels flips. For
$\delta_1=\delta_2=0.1$ the flip probability is $0.18$ and $C=1-\hb(0.18)\approx0.320$, less than $0.531$.

\sol{9.3} The output blocks take two values, so $H_n(\eta)=1$ and $H(\eta)=0$. Since $\omega=\mu\otimes\eta$,
$H_n(\omega)=H_n(\mu)+1$ and $H(\omega)=H(\mu)$. Hence $R(\mu,\nu)=0$, as it must be for a channel that ignores its input.

\sol{9.4} For inputs $(X,X')$ to the product channel, $Y$ and $Y'$ are conditionally independent given
$(X,X')$ with $H(YY'\st XX')=H(Y\st X)+H(Y'\st X')$, and $H(YY')\le H(Y)+H(Y')$; so
$I(XX';YY')\le I(X;Y)+I(X';Y')\le C(W)+C(W')$. Independent optimal inputs attain the bound. For the sum channel
let $\lambda$ be the probability of using the first component. The output determines the component, so
$I=\hb(\lambda)+\lambda I_1+(1-\lambda)I_2$, maximal over the conditional inputs at $\hb(\lambda)+\lambda C+(1-\lambda)C'$ and then over
$\lambda$ at $\lambda=2^C/(2^C+2^{C'})$, with value $\log(2^C+2^{C'})$.

\sol{9.5} Naturality for maps says that the first $n$ letters of $\nu_{n+1}(x_1\dots x_{n+1})$ are
$\nu_n(x_1\dots x_n)$, so the $n$-th output letter is a function $f_n$ of $x_1,\dots,x_n$, and any such sequence of
functions is natural. For $y_n=x_{n+1}$ the law of $y_1$ depends on $x_2$ and is not a function of $x_1$.
%% ---- end sol/09.tex ----
%% ---- begin sol/10.tex ----
\section*{Chapter 10}

\sol{10.1} On $E_x$ we have $Q(y)<W(y\st x)\,2^{-\gamma}/M$. Summing over $y\in E_x$ gives
$Q(E_x)\le W(E_x\st x)\,2^{-\gamma}/M\le2^{-\gamma}/M$.

\sol{10.2} With uniform inputs the output is uniform, $Q(y)=2^{-n}$, and $W(y\st x)=\delta^d(1-\delta)^{n-d}$. Since
$\delta<\tfrac12$ the density decreases in $d$ and $E_x$ is a ball. For $n=7$, $\delta=0.01$: $i=6.898$ at $d=0$ and
$0.269$ at $d=1$. With $\log M=4$ and $\gamma>0$ the threshold $4+\gamma$ exceeds $0.269$, so $E_x=\{x\}$ and one needs
$\gamma<2.898$. The guaranteed error is then $\Prob[d\ge1]+2^{-\gamma}$, with infimum
$(1-0.99^7)+2^{-2.898}\approx0.068+0.134=0.202$. The Hamming code corrects one error and fails with probability
$1-0.99^7-7(0.01)(0.99)^6\approx0.0020$. The lemma is sharp in rate and far from sharp at length seven.

\sol{10.3} Identity: $W(D_j\st x_j)\ge1-\varepsilon>0$ forces $x_j\in D_j$, and the sets are disjoint, so the codewords
are distinct and $M^*=k$ for every $\varepsilon<1$. Constant channel with output law $Q$: one needs disjoint sets of
$Q$-measure at least $1-\varepsilon$, so $M^*\le\lfloor1/(1-\varepsilon)\rfloor$, with $M^*=1$ for
$\varepsilon<\tfrac12$. In both cases the answer agrees with capacity $\log k$ and $0$ after taking
$\frac1n\log$ of the value for the $n$-th power.

\sol{10.4} With a stochastic encoder the $j$-th diagonal entry is $\sum_xe(x\st j)\,W(D_j\st x)\le\max_xW(D_j\st x)$, so
replacing $e(\,\cdot\st j)$ by a maximizing $x$ does not decrease it. For the second part let $Y$ be a point
and $M=2$. A deterministic decoder sends the point to one message and has maximal error $1$; a decoder that
tosses a fair coin has maximal error $\tfrac12$.

\sol{10.5} If the unerased positions distinguish $x_j$ from every other codeword, the decoder returns $x_j$.
For a linear code with a $k\times n$ generator matrix $G$ and erased set $S$, this happens for every codeword
iff the columns of $G$ outside $S$ have rank $k$, so the error probability is the same for all codewords.
Choose $G$ uniformly at random. For a fixed nonzero message $v$ the vector $vG$ restricted to the $n-|S|$
unerased positions is uniform, so it vanishes with probability $2^{-(n-|S|)}$, and the union bound gives
failure probability at most $2^{k-n+|S|}$ given $S$. With probability tending to one $|S|\le n(e+\delta)$, so the
expected failure probability is at most $2^{k-n(1-e-\delta)}+o(1)$, which is small when $k/n<1-e-2\delta$. Some $G$
does at least as well as the average.
%% ---- end sol/10.tex ----
%% ---- begin sol/11.tex ----
\section*{Chapter 11}

\sol{11.1} Huffman's procedure merges $0.1$ and $0.2$, then the result with $0.3$, then with $0.4$, giving
lengths $(1,2,3,3)$ and codewords $0,10,110,111$. The expected length is $0.4+0.6+0.6+0.3=1.9$ and
$H(p)\approx1.846$.

\sol{11.2} In the proof of \cref{thm:noiseless}, $L-H(p)=\KL pq-\log K$ with both terms nonnegative. Equality
needs $K=1$ and $p=q$, so $p(x)=2^{-\ell(x)}$. Conversely if every $p(x)$ is a power of $\tfrac12$ the lengths
$-\log p(x)$ satisfy Kraft's inequality with equality.

\sol{11.3} Let the channel code have $M$ messages, of which message $1$ is always decoded wrongly and the
others always correctly; its average error is $1/M$. Let the compression send a set of source blocks of
probability $0.9$ to message $1$. The composite fails with probability at least $0.9$. Repair: discard the
worse half of the messages. If the average error is $\varepsilon$, at most half of the messages have error above
$2\varepsilon$, so the remaining $M/2$ form a code with maximal error $2\varepsilon$, at a cost of one bit.

\sol{11.4} If $f$ factors through $[r]$ so does every composite with $f$, which gives (i); if $f,g$ factor
through $[r],[s]$ then $f\otimes g$ factors through $[rs]$, which gives (ii). For (iii), if $f\colon[M]\to[M]$ has
diagonal at least $1-\varepsilon$ and factors through $[r]$, then
$(1-\varepsilon)\log M-1\le C(f)\le\log r$ by Fano's inequality and \cref{prop:capacity}(iv). The bound is
$\frac1n\log M^*(W^{\otimes n},\varepsilon)\le(\log r_+(W)+\frac1n)/(1-\varepsilon)$. For a binary symmetric channel with
$0<\delta<\tfrac12$, $r_+=2$ and $\Phi=1>1-\hb(\delta)$. The function $\log\min\{|X|,|Y|\}$ fails (i): a composite
$X\to1\to X$ has $\Phi=\log|X|$ while each factor has $\Phi=0$.

\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 is
erased; the erasure probability is $1-(1-e)^2$. $W^+$: given $u_1$, the bit $u_2$ equals $x_2$ and equals
$x_1\oplus u_1$, so it is unknown iff both outputs are erased, with probability $e^2$. Next,
$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 inequality
$\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)$ over
the $2^n$ channels is at most $(\tfrac{\sqrt3}{2})^n f(e)$, and by Markov's inequality the fraction with
$e_b\in[\delta,1-\delta]$, where $f\ge\sqrt{\delta(1-\delta)}$, tends to zero geometrically. The mean of $e_b$ is
conserved, so the fraction with $e_b<\delta$ tends to $1-e$.
%% ---- end sol/11.tex ----
%% ---- begin sol/12.tex ----
\section*{Chapter 12}

\sol{12.1} In $C_5$ any three vertices contain two adjacent ones, and $\{0,2\}$ is independent. Two words
$(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\}$ modulo
$5$; for $i-j=\pm1$ the second difference is $\pm2$. For the capacity, $H(Y\st X)=1$ for every input and
the uniform input gives the uniform output, so $C=\log5-1$.

\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$,
and $H_\alpha=\frac1{1-\alpha}\log\sum p^\alpha$ increases. For $\alpha>1$ the inequality reverses and so does the sign of
$1-\alpha$. The cases $\alpha=0,1,\infty$ follow by continuity, or directly. Then use additivity:
$H_\alpha(p^{\otimes n})=nH_\alpha(p)$.

\sol{12.3} (i) Every block in the support has positive probability, so $d\circ e$ must be the identity on all
$|\supp p|^n$ of them, and conversely that many messages suffice. For the numbers: $\hb(\tau)=0.7$ gives
$\tau\approx0.1893$, and $\KL{(1-\tau,\tau)}{p}\approx0.0521$. The supremum of $\rho(0.7-H_{1/(1+\rho)}(p))$ is attained near
$\rho\approx0.51$ and is also $0.0521$. The first expression is the exponent of the probability that a block has
more than $\tau n$ ones, which is the event that the best set of $2^{nR}$ blocks misses it.

\sol{12.4} Let $a_n$ be the number of allowed blocks of length $n$. An allowed block ends in $0$, preceded by
any allowed block of length $n-1$, or in $01$, preceded by any allowed block of length $n-2$; so
$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 chain
with $q_{01}=a$ and $q_{10}=1$ has stationary distribution $(\frac1{1+a},\frac{a}{1+a})$ and entropy $\hb(a)/(1+a)$. Its
derivative 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 the
maximum is $\log\phi$.

\sol{12.5} The entropies are $1$, $\log3\approx1.585$, $2$ and $2$. By \cref{thm:ornstein} and \cref{thm:KS}, one
Bernoulli shift is a factor of another iff its entropy is not larger. So $B(\tfrac12,\tfrac12)$ is a factor of
the other three, $B(\tfrac13,\tfrac13,\tfrac13)$ is a factor of Meshalkin's two, and those two are isomorphic. No
other factor relations hold.
%% ---- end sol/12.tex ----
\backmatter
%% ---- begin bib.tex ----
\chapter{References}
\begingroup\small
\renewcommand{\chapter}[2]{}
\begin{thebibliography}{FGLPS26}\setlength{\itemsep}{1pt}
\newcommand{\bi}[1]{\bibitem[#1]{#1}}
\bi{AC88} P. Algoet and T. Cover. A sandwich proof of the Shannon--McMillan--Breiman theorem. \emph{Ann. Probab.} 16 (1988).
\bi{AD75} J. Acz\'el and Z. Dar\'oczy. \emph{On Measures of Information and Their Characterizations}. Academic Press, 1975.
\bi{Adl61} R. Adler. Ergodic and mixing properties of infinite memory channels. \emph{Proc. Amer. Math. Soc.} 12 (1961).
\bi{Alo98} N. Alon. The Shannon capacity of a union. \emph{Combinatorica} 18 (1998).
\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).
\bi{AT09} E. Ar\i kan and E. Telatar. On the rate of channel polarization. \emph{Proc. IEEE ISIT} (2009).
\bi{BB15} P. Baudot and D. Bennequin. The homological nature of entropy. \emph{Entropy} 17 (2015).
\bi{BF14} J. Baez and T. Fritz. A Bayesian characterization of relative entropy. \emph{Theory Appl. Categ.} 29 (2014).
\bi{BFL11} J. Baez, T. Fritz and T. Leinster. A characterization of entropy in terms of information loss. \emph{Entropy} 13 (2011).
\bi{Bil65} P. Billingsley. \emph{Ergodic Theory and Information}. Wiley, 1965.
\bi{Bir31} G. D. Birkhoff. Proof of the ergodic theorem. \emph{Proc. Nat. Acad. Sci. USA} 17 (1931).
\bi{Bla57} D. Blackwell. The entropy of functions of finite-state Markov chains. \emph{Trans. First Prague Conf. Information Theory} (1957).
\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).
\bi{Bra21} T.-D. Bradley. Entropy as a topological operad derivation. \emph{Entropy} 23 (2021).
\bi{Bre57} L. Breiman. The individual ergodic theorem of information theory. \emph{Ann. Math. Statist.} 28 (1957); correction, 31 (1960).
\bi{Bre60} L. Breiman. On achieving channel capacity in finite-memory channels. \emph{Illinois J. Math.} 4 (1960).
\bi{Cat88} J.-L. Cathelineau. Sur l'homologie de $\mathrm{SL}_2$ \`a coefficients dans l'action adjointe. \emph{Math. Scand.} 63 (1988).
\bi{Cen82} N. N. \v{C}encov. \emph{Statistical Decision Rules and Optimal Inference}. Amer. Math. Soc., 1982.
\bi{CFS16} B. Coecke, T. Fritz and R. Spekkens. A mathematical theory of resources. \emph{Inform. and Comput.} 250 (2016).
\bi{Chu61} K. L. Chung. A note on the ergodic theorem of information theory. \emph{Ann. Math. Statist.} 32 (1961).
\bi{CJ19} K. Cho and B. Jacobs. Disintegration and Bayesian inversion via string diagrams. \emph{Math. Structures Comput. Sci.} 29 (2019).
\bi{CK11} I. Csisz\'ar and J. K\"orner. \emph{Information Theory: Coding Theorems for Discrete Memoryless Systems}, 2nd ed. Cambridge Univ. Press, 2011.
\bi{CT06} T. Cover and J. Thomas. \emph{Elements of Information Theory}, 2nd ed. Wiley, 2006.
\bi{Dar70} Z. Dar\'oczy. Generalized information functions. \emph{Inform. and Control} 16 (1970).
\bi{DDGK16} F. Dahlqvist, V. Danos, I. Garnier and O. Kammar. Bayesian inversion by $\omega$-complete cone duality. \emph{Proc. CONCUR 2016}.
\bi{DGB13} D. Dikranjan and A. Giordano Bruno. Entropy in a category. \emph{Appl. Categ. Structures} 21 (2013).
\bi{DHKK14} G. Dimitrov, F. Haiden, L. Katzarkov and M. Kontsevich. Dynamical systems and categories. \emph{Contemp. Math.} 621 (2014).
\bi{Dob59} R. L. Dobrushin. General formulation of Shannon's main theorem in information theory. \emph{Uspekhi Mat. Nauk} 14 (1959).
\bi{Doo53} J. L. Doob. \emph{Stochastic Processes}. Wiley, 1953.
\bi{EP23} N. Ensarguet and P. Perrone. Categorical probability spaces, ergodic decompositions, and transitions to equilibrium. arXiv:2310.04267 (2023).
\bi{Erd46} P. Erd\H{o}s. On the distribution function of additive functions. \emph{Ann. of Math.} 47 (1946).
\bi{EVG02} P. Elbaz-Vincent and H. Gangl. On poly(ana)logs I. \emph{Compositio Math.} 130 (2002).
\bi{Fad56} D. K. Faddeev. On the concept of entropy of a finite probabilistic scheme. \emph{Uspekhi Mat. Nauk} 11 (1956).
\bi{Fan61} R. Fano. \emph{Transmission of Information}. MIT Press, 1961.
\bi{Fei54} A. Feinstein. A new basic theorem of information theory. \emph{IRE Trans. Inform. Theory} 4 (1954).
\bi{Fei58} A. Feinstein. \emph{Foundations of Information Theory}. McGraw-Hill, 1958.
\bi{Fei59} A. Feinstein. On the coding theorem and its converse for finite-memory channels. \emph{Inform. and Control} 2 (1959).
\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).
\bi{FR20} T. Fritz and E. F. Rischel. Infinite products and zero-one laws in categorical probability. \emph{Compositionality} 2 (2020).
\bi{Fri17} T. Fritz. Resource convertibility and ordered commutative monoids. \emph{Math. Structures Comput. Sci.} 27 (2017).
\bi{Fri20} T. Fritz. A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics. \emph{Adv. Math.} 370 (2020).
\bi{Fuj78} S. Fujishige. Polymatroidal dependence structure of a set of random variables. \emph{Inform. and Control} 39 (1978).
\bi{FuP21} J. Fullwood and A. Parzygnat. The information loss of a stochastic map. \emph{Entropy} 23 (2021).
\bi{Gir82} M. Giry. A categorical approach to probability theory. \emph{Lecture Notes in Math.} 915 (1982).
\bi{Gla03} E. Glasner. \emph{Ergodic Theory via Joinings}. Amer. Math. Soc., 2003.
\bi{Gra09} R. Gray. \emph{Probability, Random Processes, and Ergodic Properties}, 2nd ed. Springer, 2009.
\bi{Gra11} R. Gray. \emph{Entropy and Information Theory}, 2nd ed. Springer, 2011.
\bi{Gro13} M. Gromov. In a search for a structure, Part 1: On entropy. Preprint, 2013.
\bi{Hae79} W. Haemers. On some problems of Lov\'asz concerning the Shannon capacity of a graph. \emph{IEEE Trans. Inform. Theory} 25 (1979).
\bi{Han03} T. S. Han. \emph{Information-Spectrum Methods in Information Theory}. Springer, 2003.
\bi{HC67} J. Havrda and F. Charv\'at. Quantification method of classification processes: concept of structural $a$-entropy. \emph{Kybernetika} 3 (1967).
\bi{Hed69} G. Hedlund. Endomorphisms and automorphisms of the shift dynamical system. \emph{Math. Systems Theory} 3 (1969).
\bi{HJS07} I. Hasuo, B. Jacobs and A. Sokolova. Generic trace semantics via coinduction. \emph{Log. Methods Comput. Sci.} 3(4) (2007).
\bi{Hu62} Hu Kuo Ting. On the amount of information. \emph{Theory Probab. Appl.} 7 (1962).
\bi{Huf52} D. Huffman. A method for the construction of minimum-redundancy codes. \emph{Proc. IRE} 40 (1952).
\bi{HV93} T. S. Han and S. Verd\'u. Approximation theory of output statistics. \emph{IEEE Trans. Inform. Theory} 39 (1993).
\bi{Jac59} K. Jacobs. Die \"Ubertragung diskreter Informationen durch periodische und fastperiodische Kan\"ale. \emph{Math. Ann.} 137 (1959).
\bi{JV20} A. Jensen and P. Vrana. The asymptotic spectrum of LOCC transformations. \emph{IEEE Trans. Inform. Theory} 66 (2020).
\bi{Ken64} D. G. Kendall. Functional equations in information theory. \emph{Z. Wahrscheinlichkeitstheorie verw. Gebiete} 2 (1964).
\bi{Khi53} A. I. Khinchin. The entropy concept in probability theory. \emph{Uspekhi Mat. Nauk} 8(3) (1953). English translation in \cite{Khi57}.
\bi{Khi56} A. I. Khinchin. On the fundamental theorems of information theory. \emph{Uspekhi Mat. Nauk} 11(1) (1956). English translation in \cite{Khi57}.
\bi{Khi57} A. I. Khinchin. \emph{Mathematical Foundations of Information Theory}. Translated by R. A. Silverman and M. D. Friedman. Dover, 1957.
\bi{KK13} H. Kerstan and B. K\"onig. Coalgebraic trace semantics for continuous probabilistic transition systems. \emph{Log. Methods Comput. Sci.} 9(4) (2013).
\bi{Kli07} M. Klimesh. Inequalities that collectively completely characterize the catalytic majorization relation. arXiv:0709.3680 (2007).
\bi{Kol58} A. N. Kolmogorov. A new metric invariant of transient dynamical systems and automorphisms in Lebesgue spaces. \emph{Dokl. Akad. Nauk SSSR} 119 (1958).
\bi{Kon95} M. Kontsevich. The $1\frac12$-logarithm. Appendix to \cite{EVG02}; circulated 1995.
\bi{Kra49} L. G. Kraft. A device for quantizing, grouping, and coding amplitude-modulated pulses. M.S. thesis, MIT, 1949.
\bi{Kri70} W. Krieger. On entropy and generators of measure-preserving transformations. \emph{Trans. Amer. Math. Soc.} 149 (1970).
\bi{Law62} F. W. Lawvere. The category of probabilistic mappings. Unpublished manuscript, 1962.
\bi{Law73} F. W. Lawvere. Metric spaces, generalized logic, and closed categories. \emph{Rend. Sem. Mat. Fis. Milano} 43 (1973).
\bi{Lee64} P. M. Lee. On the axioms of information theory. \emph{Ann. Math. Statist.} 35 (1964).
\bi{Lei21} T. Leinster. \emph{Entropy and Diversity: The Axiomatic Approach}. Cambridge Univ. Press, 2021.
\bi{Lei21p} T. Leinster. Entropy modulo a prime. \emph{Commun. Number Theory Phys.} 15 (2021).
\bi{Lin01} E. Lindenstrauss. Pointwise theorems for amenable groups. \emph{Invent. Math.} 146 (2001).
\bi{LM95} D. Lind and B. Marcus. \emph{An Introduction to Symbolic Dynamics and Coding}. Cambridge Univ. Press, 1995.
\bi{Lov79} L. Lov\'asz. On the Shannon capacity of a graph. \emph{IEEE Trans. Inform. Theory} 25 (1979).
\bi{Mat07} F. Mat\'u\v{s}. Infinitely many information inequalities. \emph{Proc. IEEE ISIT} (2007).
\bi{McM53} B. McMillan. The basic theorems of information theory. \emph{Ann. Math. Statist.} 24 (1953).
\bi{McM56} B. McMillan. Two inequalities implied by unique decipherability. \emph{IRE Trans. Inform. Theory} 2 (1956).
\bi{Mes59} L. D. Meshalkin. A case of isomorphism of Bernoulli schemes. \emph{Dokl. Akad. Nauk SSSR} 128 (1959).
\bi{MP23} S. Moss and P. Perrone. A category-theoretic proof of the ergodic decomposition theorem. \emph{Ergodic Theory Dynam. Systems} 43 (2023).
\bi{Ned57} J. Nedoma. The capacity of a discrete channel. \emph{Trans. First Prague Conf. Information Theory} (1957).
\bi{Orn70} D. Ornstein. Bernoulli shifts with the same entropy are isomorphic. \emph{Adv. Math.} 4 (1970).
\bi{OW83} D. Ornstein and B. Weiss. The Shannon--McMillan--Breiman theorem for a class of amenable groups. \emph{Israel J. Math.} 44 (1983).
\bi{Par61} K. R. Parthasarathy. On the integral representation of the rate of transmission of a stationary channel. \emph{Illinois J. Math.} 5 (1961).
\bi{Par64} W. Parry. Intrinsic Markov chains. \emph{Trans. Amer. Math. Soc.} 112 (1964).
\bi{Par22} A. Parzygnat. A functorial characterization of von Neumann entropy. \emph{Cah. Topol. G\'eom. Diff\'er. Cat\'eg.} 63 (2022).
\bi{Per24} P. Perrone. Markov categories and entropy. \emph{IEEE Trans. Inform. Theory} 70 (2024).
\bi{Pet83} K. Petersen. \emph{Ergodic Theory}. Cambridge Univ. Press, 1983.
\bi{PVB24} P. Perrone and R. Van Belle. Convergence of martingales via enriched dagger categories. arXiv:2404.15191 (2024).
\bi{PW25} Y. Polyanskiy and Y. Wu. \emph{Information Theory: From Coding to Learning}. Cambridge Univ. Press, 2025.
\bi{Ren61} A. R\'enyi. On measures of entropy and information. \emph{Proc. Fourth Berkeley Symp. Math. Statist. Probab.} 1 (1961).
\bi{SBBR13} A. Silva, F. Bonchi, M. Bonsangue and J. Rutten. Generalizing determinization from automata to coalgebras. \emph{Log. Methods Comput. Sci.} 9(1) (2013).
\bi{Sha48} C. E. Shannon. A mathematical theory of communication. \emph{Bell System Tech. J.} 27 (1948).
\bi{Sha56} C. E. Shannon. The zero error capacity of a noisy channel. \emph{IRE Trans. Inform. Theory} 2 (1956).
\bi{Sin59} Ya. G. Sinai. On the concept of entropy for a dynamical system. \emph{Dokl. Akad. Nauk SSSR} 124 (1959).
\bi{Sin64} Ya. G. Sinai. On a weak isomorphism of transformations with invariant measure. \emph{Mat. Sb.} 63 (1964).
\bi{SP82} M. Smyth and G. Plotkin. The category-theoretic solution of recursive domain equations. \emph{SIAM J. Comput.} 11 (1982).
\bi{SSZ05} I. Sutskover, S. Shamai and J. Ziv. Extremes of information combining. \emph{IEEE Trans. Inform. Theory} 51 (2005).
\bi{Str88} V. Strassen. The asymptotic spectrum of tensors. \emph{J. Reine Angew. Math.} 384 (1988).
\bi{Tak58} K. Takano. On the basic theorems of information theory. \emph{Ann. Inst. Statist. Math.} 9 (1958).
\bi{Tsa88} C. Tsallis. Possible generalization of Boltzmann--Gibbs statistics. \emph{J. Statist. Phys.} 52 (1988).
\bi{Tur07} S. Turgut. Catalytic transformations for bipartite pure states. \emph{J. Phys. A} 40 (2007).
\bi{Tve58} H. Tverberg. A new derivation of the information function. \emph{Math. Scand.} 6 (1958).
\bi{VB23} R. Van Belle. A categorical treatment of the Radon--Nikodym theorem and martingales. arXiv preprint (2023).
\bi{VH94} S. Verd\'u and T. S. Han. A general formula for channel capacity. \emph{IEEE Trans. Inform. Theory} 40 (1994).
\bi{Vig19} J. P. Vigneaux. \emph{Topology of Statistical Systems: A Cohomological Approach to Information Theory}. Thesis, Universit\'e Paris Diderot, 2019.
\bi{Vig20} J. P. Vigneaux. Information structures and their cohomology. \emph{Theory Appl. Categ.} 35 (2020).
\bi{vN32} J. von Neumann. Proof of the quasi-ergodic hypothesis. \emph{Proc. Nat. Acad. Sci. USA} 18 (1932).
\bi{VVS95} S. Vembu, S. Verd\'u and Y. Steinberg. The source-channel separation theorem revisited. \emph{IEEE Trans. Inform. Theory} 41 (1995).
\bi{Wal82} P. Walters. \emph{An Introduction to Ergodic Theory}. Springer, 1982.
\bi{Wol57} J. Wolfowitz. The coding of messages subject to chance errors. \emph{Illinois J. Math.} 1 (1957).
\bi{Wol78} J. Wolfowitz. \emph{Coding Theorems of Information Theory}, 3rd ed. Springer, 1978.
\bi{WZ73} A. Wyner and J. Ziv. A theorem on the entropy of certain binary sequences and applications: Part I. \emph{IEEE Trans. Inform. Theory} 19 (1973).
\bi{Yeu08} R. Yeung. \emph{Information Theory and Network Coding}. Springer, 2008.
\bi{Zui19} J. Zuiddam. The asymptotic spectrum of graphs and the Shannon capacity. \emph{Combinatorica} 39 (2019).
\bi{ZY98} Z. Zhang and R. Yeung. On characterization of entropy function via information inequalities. \emph{IEEE Trans. Inform. Theory} 44 (1998).
\end{thebibliography}
\endgroup
%% ---- end bib.tex ----
\end{document}
