10 Generators: Shannon–McMillan–Breiman and Krieger’s theorem

The Kolmogorov–Sinai entropy of the classical-entropy development measures the average information produced by a transformation per unit time. This chapter documents the generator side of that theory (the 29 modules of ErgodicTheory/Krieger/): the pointwise Shannon–McMillan–Breiman theorem (entropy equipartition), the Rokhlin–Kakutani tower lemma, the symbolic coding stack built on them (name counting and sentinel prefix codes), and the two generator headliners — the countable finite-entropy two-sided generator of Rokhlin, Keane–Serafin and Downarowicz, and Krieger’s finite generator theorem: an ergodic aperiodic automorphism of entropy below $\log k$ admits a two-sided generating partition with at most $k$ cells.

Throughout, $(\alpha ,\mu )$ is a probability space, $T$ a measure-preserving transformation, and $P$ a finite measurable partition indexed by a finite type $\iota $ (a MeasurePartition: measurable cells, pairwise a.e.-disjoint, covering $\alpha $). For the coding and generator layers, $e$ is a measure-preserving automorphism (a measurable equivalence $\alpha \simeq \alpha $) of a standard Borel probability space and iterates range over $\mathbb {Z}$. We write $\bigvee _{k=0}^{n-1} T^{-k}P$ for the $n$-fold iterated join, $H(\cdot )$ for Shannon entropy, and $h(P,T)$ for the Kolmogorov–Sinai entropy of the pair. Every result below is formalized sorry-free; the two headline generator theorems are stated relative to explicitly disclosed hypothesis bundles (their honest formalization boundary, described in place).

10.1 The information function and its chain rules

Definition 10.1 Information function of the iterated join

✓

Every point $x$ has an $n$-step itinerary $f : \operatorname {Fin}n \to \iota $, recording for each $k {\lt} n$ which cell of $P$ contains $T^k x$; among the admissible codes the least one in a fixed enumeration is chosen, which makes the selector genuinely measurable (the cells may overlap on a null set, so a bare choice function would not be). The atom of $x$ is the cell $\bigcap _{k{\lt}n} T^{-k}(P_{f(k)})$ of the iterated join containing $x$, and the information function is

\[ i_n(x) \; =\; -\log \mu \bigl(\mathrm{atom}_n(x)\bigr), \]

the surprise of learning the $n$-name of $x$. It is nonnegative and measurable (): in its simple-function form it is a finite sum of indicators of the itinerary fibers, each the difference of a join cell and the finitely many strictly smaller cells.

Theorem 10.2 The information function integrates to the join entropy

✓

For every $n$,

\[ \int _\alpha i_n \, d\mu \; =\; H\Bigl(\bigvee _{k=0}^{n-1} T^{-k}P\Bigr), \]

the Shannon entropy of the $n$-fold iterated join (the $n$-th term of the Kolmogorov–Sinai entropy sequence).

Proof ▶

Write $i_n$ as the finite sum of indicators of the itinerary fibers weighted by $-\log \mu (\text{cell})$ and integrate termwise. Each fiber differs from its join cell only inside the union of the other cells — a null set by pairwise a.e.-disjointness — so fiber and cell have the same measure, and each summand becomes $\mu (\text{cell})\cdot (-\log \mu (\text{cell})) = \operatorname {negMulLog}\mu (\text{cell})$, which summed over the cells is the join entropy.

Theorem 10.3 Telescoped Breiman chain rule, entropy level

✓

On a standard Borel space, the $n$-step join entropy telescopes into conditional entropies:

\[ H\Bigl(\bigvee _{k=0}^{n-1} T^{-k}P\Bigr) \; =\; \sum _{k=0}^{n-1} H\Bigl(P \, \Big|\, \sigma \bigl(T^{-1}\textstyle \bigvee _{j=0}^{k-1} T^{-j}P\bigr)\Bigr), \]

where the $k$-th conditioning $\sigma $-algebra is generated by the cells of the $T$-pullback of the $k$-step join.

Proof ▶

Induction on $n$ from the one-step chain rule: reindexing along $\operatorname {Fin}n \times \iota \simeq \operatorname {Fin}(n{+}1)$ (peeling the first symbol) identifies the $(n{+}1)$-fold join with the join $B \vee P$, $B := T^{-1}(\bigvee _0^{n-1}T^{-k}P)$; the absolute chain rule $H(B \vee P) = H(B) + H(P \mid B)$ and $T$-invariance of join entropy give $H(\bigvee _0^{n}) = H(\bigvee _0^{n-1}) + H(P \mid \sigma (B))$, the conditional entropy bridged from its additive-over-cells form to the $\sigma $-algebra form.

Theorem 10.4 The sharp KS rate as a conditional entropy

✓

On a standard Borel space (with $\iota $ nonempty), the Kolmogorov–Sinai entropy of the pair equals the conditional entropy of $P$ given the $\sigma $-algebra of the strict future:

\[ h(P,T) \; =\; H\Bigl(P \, \Big|\, \bigvee _{k}\sigma \bigl(T^{-1}\textstyle \bigvee _{j=0}^{k-1} T^{-j}P\bigr)\Bigr) \; =\; H\Bigl(P \, \Big|\, \sigma \Bigl(\bigvee _{j\ge 1} T^{-j}P\Bigr)\Bigr). \]

This is the integral-level statement of the sharp SMB rate: the precise constant the pointwise theorem converges to. No ergodicity is needed.

Proof ▶

The conditioning $\sigma $-algebras increase in $k$, so the fixed-partition Lévy theorem (martingale convergence of conditional entropies) sends $H(P \mid \sigma _k) \to H(P \mid \bigvee _k \sigma _k)$. By Theorem 10.3, $\tfrac 1n H(\bigvee _0^{n-1}T^{-k}P)$ is exactly the Cesàro average of that convergent sequence, hence tends to the same limit; matching it against the Fekete limit defining $h(P,T)$ gives the identity.

10.2 The pointwise Shannon–McMillan–Breiman theorem

Theorem 10.5 Crude name-count bound, Birkhoff-free

✓

For a measure-preserving $T$ and a finite partition indexed by a nonempty $\iota $,

\[ \limsup _{n\to \infty } \frac{i_n(x)}{n} \; \le \; \log \# \iota \qquad \text{for $\mu $-a.e.\ } x. \]

Neither ergodicity nor any ergodic theorem enters: this is the Algoet–Cover engine fed the uniform competing measure, whose partition-function bound $\int \exp \bigl(i_n - n\log \# \iota \bigr)\, d\mu \le 1$ is the lemma .

Proof ▶

On each itinerary fiber the integrand $\exp (i_n - n\log \# \iota )$ is the constant $\mu (\text{cell})^{-1}\cdot (\# \iota )^{-n}$ (or vanishes with the cell), and the join has at most $(\# \iota )^n$ non-null cells, giving the partition-function bound. Markov’s inequality plus Borel–Cantelli then make $\tfrac 1n i_n \le \log \# \iota + \varepsilon $ eventually a.e. for every $\varepsilon {\gt} 0$.

Definition 10.6 Conditional information function

✓

For a sub-$\sigma $-algebra $\mathcal A$ of a standard Borel space, the conditional information function of $P$ given $\mathcal A$ is

\[ g_{\mathcal A}(x) \; =\; \sum _i \mathbf1_{P_i}(x)\cdot \bigl(-\log \mu [P_i \mid \mathcal A](x)\bigr), \]

the conditional probability realized by the regular conditional probability kernel; exactly one indicator survives at each point. Its integral is the conditional entropy: for $\mathcal A \le m_\alpha $, $\int g_{\mathcal A}\, d\mu = H(P \mid \mathcal A)$ (); in particular $g_{\mathcal A}$ is integrable.

Theorem 10.7 Chung’s maximal inequality

✓

Let $g_k$ be the conditional information function of $P$ given the $k$-th Breiman conditioning $\sigma $-algebra $\mathcal C_k = \sigma (T^{-1}\bigvee _{j=0}^{k-1}T^{-j}P)$, and let $g^{*} = \sup _k g_k$ be the Chung maximal information function (, valued in $[0,\infty ]$). Then for every cell $P_{i_0}$ and every $\lambda {\gt} 0$,

\[ \mu \bigl(\{ x \in P_{i_0} \mid g^{*}(x) {\gt} \lambda \} \bigr) \; \le \; e^{-\lambda }. \]

Consequently $g^{*} \in L^1(\mu )$, with $\int g^{*}\, d\mu \le H(P) + 1$ () — Chung’s $L^1$ domination, the one genuinely analytic leaf of the SMB proof.

Proof ▶

A stopping-time (first-passage) argument: stratify $\{ g^{*} {\gt} \lambda \} \cap P_{i_0}$ by the first level $k$ at which the conditional probability of $P_{i_0}$ drops below $e^{-\lambda }$. Each stratum is $\mathcal C_k$-measurable, so its intersection with $P_{i_0}$ has measure at most $e^{-\lambda }$ times the stratum’s measure by the defining property of conditional probability; summing the disjoint strata gives the tail bound. Integrability follows by the layer-cake formula: summing the per-cell tails yields $\int g^{*} \le H(P) + 1$.

Theorem 10.8 Pointwise SMB, from the Breiman telescoping

✓

Let $T$ be ergodic and let $(i_n)$ be any sequence of functions satisfying, for $\mu $-a.e. $x$ and all $n$, the Breiman telescoping identity

\[ i_n(x) \; =\; \sum _{j=0}^{n-1} g_{n-j}(T^{j}x), \]

where $g_k$ is the conditional information function of $P$ given $\mathcal C_k$. Then

\[ \frac{i_n(x)}{n} \; \longrightarrow \; h(P,T) \qquad \text{for $\mu $-a.e.\ } x. \]

Proof ▶

Split $\tfrac 1n\sum _{j{\lt}n} g_{n-j}(T^jx)$ into the Birkhoff main term $\tfrac 1n\sum _{j{\lt}n} g_\infty (T^jx)$ and the Cesàro tail $\tfrac 1n\sum _{j{\lt}n}(g_{n-j}-g_\infty )(T^jx)$, where $g_\infty $ is the conditional information function given the strict-future $\sigma $-algebra $\bigvee _k \mathcal C_k$. The main term converges a.e. to $\int g_\infty \, d\mu = h(P,T)$ by the pointwise ergodic theorem and the sharp rate identity (Theorem 10.4). The tail vanishes a.e. by the Maker/Breiman dominated-Cesàro argument (): $|g_{n-j}-g_\infty |$ is dominated by the integrable maximal function $g^{*} + g_\infty $ of Theorem 10.7, and Lévy downward convergence $g_k \to g_\infty $ a.e. makes the dominated Birkhoff averages of the sup-tails vanish.

Theorem 10.9 Pointwise Shannon–McMillan–Breiman theorem

✓

Let $T$ be an ergodic measure-preserving transformation of a standard Borel probability space and $P$ a finite measurable partition (nonempty index). Then the concrete information functions of Definition 10.1 satisfy

\[ \frac{i_n(x)}{n} \; \longrightarrow \; h(P,T) \qquad \text{for $\mu $-a.e.\ } x : \]

the measure of the atom of $x$ in the $n$-fold join decays like $e^{-n\, h(P,T)}$ (entropy equipartition, the AEP of ergodic theory).

Proof ▶

The one-step factorization of the information weight (peeling the first symbol of the itinerary) telescopes, a.e., the concrete $i_{n+1}(x)$ into the Breiman partial sum $\sum _{j{\lt}n} g_{n-j}(T^jx)$ plus a single edge term $g_0(T^n x)$. The partial sum converges after division by $n$ via Theorem 10.8; the edge term dies since $\tfrac 1n g_0(T^n x) \to 0$ a.e. for the integrable $g_0$; an index shift finishes.

Theorem 10.10 In-measure upper equipartition

✓

For ergodic $T$, the in-measure SMB upper bound holds: for every $\varepsilon {\gt} 0$,

\[ \mu \Bigl(\Bigl\{ x \; \Big|\; h(P,T) + \varepsilon {\lt} \tfrac 1N\, i_N(x)\Bigr\} \Bigr) \; \longrightarrow \; 0 \qquad (N \to \infty ). \]

This McMillan-type form is exactly what the name-count covering bound below consumes.

Proof ▶

Almost-everywhere convergence (Theorem 10.9) makes the deviation sets eventually empty along a.e. orbit; convergence in measure of their indicators to the empty set follows on the finite measure space.

10.3 The Rokhlin tower lemma

Theorem 10.11 Rokhlin–Kakutani tower lemma

✓

Let $e$ be an ergodic measure-preserving automorphism of a standard Borel probability space with non-atomic $\mu $. For every height $N \ge 1$ and every $\varepsilon {\gt} 0$ there is a measurable base $B$ whose first $N$ iterates $B, eB, \dots , e^{N-1}B$ are pairwise disjoint and whose union covers all but $\varepsilon $ of the space:

\[ \mu \Bigl(\bigcup _{i=0}^{N-1} e^{i}B\Bigr) \; {\gt}\; 1 - \varepsilon . \]

(Ergodicity plus non-atomicity supplies the aperiodicity the classical statement assumes.)

Proof ▶

The Kakutani skyscraper construction. Pick a positive measurable set $A$ with $\mu (A) {\lt} \varepsilon /N$; by ergodicity a.e. point returns to $A$, so the return-time levels of $A$ tile the space mod $0$. Grouping each return column into complete blocks of height $N$ yields the base $B$; the levels are disjoint by construction, and the uncovered part lies in the top incomplete floors of the columns, of total measure at most $N\mu (A) {\lt} \varepsilon $.

10.4 The coding stack

The passage from equipartition to a finite generator is combinatorial: count the names that carry most of the mass, encode them into a slightly larger alphabet by a prefix-free (sentinel) code painted along Rokhlin towers, and phrase “generator” as a mod-$0$ statement about the two-sided itinerary $\sigma $-algebra. We record one representative node for each layer.

Theorem 10.12 AEP covering bound: few names carry the mass

✓

Let $T$ be measure preserving and assume the in-measure SMB upper bound of Theorem 10.10. Write $h = h(P,T)$. For every $\varepsilon {\gt} 0$ and all sufficiently large $N$, there is a finite set $S$ of rank-$N$ names $g : \operatorname {Fin}N \to \iota $ with

\[ \mu \Bigl(\bigcup _{g\in S}\; \bigcap _{k{\lt}N} T^{-k}P_{g(k)}\Bigr) \; \ge \; 1 - \varepsilon \qquad \text{and}\qquad \# S \; \le \; \bigl\lfloor e^{N(h+\varepsilon )} \bigr\rfloor . \]

The set $S$ is the set of good names () — names whose join cell has measure at least $e^{-N(h+\varepsilon )}$; the cardinality bound is the unconditional pigeonhole .

Proof ▶

Pigeonhole: cells of measure $\ge e^{-N(h+\varepsilon )}$ number at most $e^{N(h+\varepsilon )}$, since they are essentially disjoint in a probability space. Coverage: the good cells cover the set $\{ \tfrac 1N i_N \le h+\varepsilon \} $, whose complement has measure ${\lt} \varepsilon $ eventually by the in-measure SMB upper bound.

Theorem 10.13 Sentinel prefix code

✓

Over an alphabet $\operatorname {Fin}l$ with a reserved sentinel letter $s$, any finite name set with $\# \mathrm{Name} \le (l-1)^m$ admits an injection $\mathrm{enc} : \mathrm{Name} \hookrightarrow \mathrm{List}(\operatorname {Fin}l)$ into blocks of length $m+1$, each containing the sentinel exactly once (at its end). The blocks form a prefix-free family, so arbitrary concatenations are uniquely decodable (); when $e^{N(h+\varepsilon )} {\lt} k^{N}$, the good names of Theorem 10.12 embed into $\operatorname {Fin}k$-blocks of length $O(N)$ — the symbolic code from which the coding partition is read off along a Rokhlin tower.

Proof ▶

The name set embeds into the fixed-length data words $\operatorname {Fin}m \to \operatorname {Fin}(l-1)$ over the non-sentinel letters by the cardinality bound; appending the sentinel produces blocks in which the sentinel marks exactly the block boundaries, so a straightforward take/drop induction recovers the block decomposition of any concatenation, giving injectivity.

Definition 10.14 Two-sided generation mod 0

✓

The two-sided saturation of a finite partition $P$ under an automorphism $e$ is the $\sigma $-algebra $\bigvee _{n\in \mathbb {Z}} e^{-n}\sigma (P)$ generated by the two-sided $P$-itinerary. The partition two-sidedly generates $(\alpha , e, \mu )$ mod $0$ when the ambient $\sigma $-algebra is contained in the $\mu $-completion of the saturation — every measurable set is recovered from the itinerary up to a null set. This mod-$0$ form (not the literal equality of $\sigma $-algebras) is the faithful conclusion of Krieger’s theorem. The $\mathrm{Countable}$-indexed analogue for a family of cells $Q : \kappa \to \mathrm{Set}\, \alpha $ is .

Definition 10.15 Countable Shannon entropy

✓

For a countable family of cells $s : \iota \to \mathrm{Set}\, \alpha $, the countable Shannon entropy is $\; c H_\mu (s) = \sum _i \operatorname {negMulLog}\, \mu (s_i) = -\sum _i \mu (s_i)\log \mu (s_i)$, an unconditionally convergent tsum. Downarowicz’s Fact 1.1.4 supplies the finiteness criterion (): if the index-weighted masses satisfy $\sum _i i\cdot \mu (s_i) {\lt} \infty $, the entropy terms are summable, so $cH_\mu (s)$ is a genuine finite sum. This is the form in which the Keane–Serafin construction certifies finite entropy of its limit partition.

10.5 The generator theorems

Theorem 10.16 Countable finite-entropy two-sided generator (Rokhlin; Keane–Serafin)

✓

Let $(\alpha ,\mu )$ be standard Borel with automorphism $e$, and let $Q : \mathbb {N}\to \mathrm{Set}\, \alpha $ be a countable family of measurable cells such that (i) the two-sided $Q$-itinerary recovers each set of a fixed standard-Borel generating sequence up to a $\mu $-null set, and (ii) the entropy terms $i \mapsto \operatorname {negMulLog}\, \mu (Q_i)$ are summable. Then there is a countable family that two-sidedly generates $(\alpha ,e,\mu )$ mod $0$ and has finite static Shannon entropy — sub-problem A of Krieger’s theorem (Downarowicz, Thm. 4.2.3, first half). The structural reduction from the inductive Keane–Serafin data — an increasing sequence of finite partitions with per-level recovery and a summable geometric mass envelope — is ; the construction of that data from the raw dynamical hypotheses (the SMB-driven Rokhlin-tower marker painting of Keane–Serafin §2) is the disclosed residual, isolated as an explicit hypothesis bundle rather than formalized.

Proof ▶

Recovering every set of a generating sequence mod $0$ pushes the ambient $\sigma $-algebra into the $\mu $-completion of the two-sided saturation of $Q$ (monotone-class/completion bookkeeping on the countable saturation), which is mod-$0$ two-sided generation; the entropy summability is carried verbatim. In the levels form, the per-level families are enumerated through the pairing bijection $\mathbb {N}\simeq \mathbb {N}\times \mathbb {N}$, the per-level recovery lifts to the union family, and the geometric envelope certifies summability via Definition 10.15.

Definition 10.17 Krieger coding data

✓

For an automorphism $e$ and $k \in \mathbb {N}$, a Krieger coding datum bundles: the measure-preservation of $e$; a countable index type $\kappa $ with measurable cells $Q : \kappa \to \mathrm{Set}\, \alpha $ two-sidedly generating mod $0$; and a $\operatorname {Fin}k$-valued partition $P$ that codes $Q$ two-sidedly mod $0$ (): the two-sided $P$-itinerary recovers each $Q$-cell up to a $\mu $-null set. This is exactly the object the Krieger construction produces when $\log k$ exceeds the entropy: $Q$ from Theorem 10.16, and $P$ from the column coding of the $\le k^{N}$ good names (Theorem 10.12 and Theorem 10.13) along refining Rokhlin towers (Theorem 10.11).

Theorem 10.18 Recovery assembly of Krieger’s theorem

✓

Given a Krieger coding datum $D$ for $(e, \mu , k)$, there exists a partition $P$ into at most $k$ cells that two-sidedly generates $(\alpha , e, \mu )$ mod $0$. No entropy, ergodicity or aperiodicity hypotheses enter: those are consumed upstream, in producing $D$. This is the pure recovery content of Krieger’s theorem.

Proof ▶

Cross-layer recovery. Mod-$0$ generation by $Q$ places the ambient $\sigma $-algebra inside the completion of the two-sided $Q$-saturation; since the $P$-itinerary recovers each $Q$-cell mod $0$, that saturation lies inside the completion of the two-sided $P$-saturation; completion-monotonicity and idempotence chain the inclusions, so $D$’s own coding partition is the generator.

Theorem 10.19 Krieger’s finite generator theorem

✓

Let $e$ be an ergodic, aperiodic (: every set of $n$-periodic points, $n \ne 0$, is $\mu $-null), measure-preserving automorphism of a probability space, and let $k \in \mathbb {N}$ satisfy

\[ h(e) \; {\lt}\; \log k, \]

where $h(e)$ is the Kolmogorov–Sinai entropy of the system. If the Krieger coding construction supplies a coding datum (Definition 10.17), then $e$ admits a finite two-sided generator of size $\le k$, mod $0$: a partition $P$ indexed by $\operatorname {Fin}k$ with $\mathrm{IsGeneratingTwoSidedMod0}\ e\ P$. The entropy threshold is pinned to the genuine $h(e)$, so the hypothesis is a real entropy constraint. Interface disclosure: the coding datum has no in-repo constructor — the tower-painting combinatorics that would discharge it from the dynamical hypotheses alone are not formalized — so this is the honest conditional form of Krieger’s theorem, with the dynamical hypotheses retained as the faithful classical interface that the upstream layers (Theorem 10.11, Theorem 10.12, Theorem 10.13 and Theorem 10.16) are designed to feed.

Proof ▶

Immediate from the recovery assembly Theorem 10.18 applied to the supplied coding datum, which already carries the measure-preservation the cross-layer recovery needs.