The Shannon-McMillan-Breiman Theorem

Intuition Beginner

Suppose a machine prints one letter per second from a small alphabet, following some fixed statistical habit, and you record the stream for a long time. How many genuinely different recordings of length $n$ are realistic? In principle a $k$-letter alphabet allows $k^n$ different strings, an astronomically large number. But almost all of those strings never actually show up: a machine that prints the letter T three times as often as H will essentially never produce a run that is half H's. The strings that do appear, with overwhelming total probability, form a much thinner crowd. The Shannon-McMillan-Breiman theorem pins down exactly how thin.

The theorem says there is a single number $h$, the entropy, such that the realistic recordings of length $n$ number about $e^{nh}$, and each of them carries roughly the same probability, about $e^{-nh}$. So out of the $k^n$ conceivable strings, only a sliver of size $e^{nh}$ matters, and within that sliver every string is about equally likely. This near-uniformity over a thin set is called the asymptotic equipartition property: long recordings spread their probability almost evenly across a typical set whose size grows at the clean exponential rate $e^{nh}$.

The practical punchline is compression. If only $e^{nh}$ recordings are realistic, you can label each one with a number that needs about $nh$ nats, ignoring the unrealistic rest at negligible cost. So $h$ is the true number of nats of information the source produces per step — the floor below which no faithful code can shrink the stream. A predictable source has small $h$ and compresses enormously; an unpredictable one has large $h$ and barely compresses at all.

The takeaway: a long output of a stationary, well-mixed source is, with near-certainty, one of about $e^{nh}$ roughly-equally-likely typical strings, so $h$ measures both how fast the realistic possibilities multiply and how few nats per symbol it takes to record the source faithfully.

Visual Beginner

Picture the full space of length-$n$ strings as a huge rectangle holding all $k^n$ possibilities, with a small shaded island inside it — the typical set — that captures nearly all of the probability while occupying almost none of the area.

The big rectangle is everything that could be printed; the shaded island is everything that realistically is printed. The island's area grows like $e^{nh}$, far smaller than the rectangle's $k^n$ whenever the source is even slightly predictable. The equal-sized dots inside the island show the equipartition: realistic strings are about equally likely, so recording which island-dot occurred takes about $nh$ nats.

Worked example Beginner

We compute the size of the typical set for a biased coin and check the equipartition by hand.

Step 1. The source. Each second the machine prints H with chance $p=0.2$ and T with chance $0.8$, independently. The per-step entropy in nats is $h=-0.2\ln 0.2-0.8\ln 0.8=0.2(1.609)+0.8(0.223)=0.322+0.178=0.500$ nats. So $h=0.5$ nats per symbol, half of the $\ln 2=0.693$ nats a fair coin would give.

Step 2. A typical string of length $n=100$. A typical recording has about $20$ H's and $80$ T's, matching the source's habit. Its probability is $0.2^{20}\times 0.8^{80}$. Take the natural log: $20\ln 0.2+80\ln 0.8=20(-1.609)+80(-0.223)=-32.2-17.9=-50.1$. So a typical string has probability about $e^{-50.1}$, which is $e^{-100\times 0.5}=e^{-nh}$, exactly the predicted $e^{-nh}$.

Step 3. Count the typical strings. If each of the typical strings has probability about $e^{-nh}$ and together they hold almost all of the probability (about $1$), then their number is about $1/e^{-nh}=e^{nh}=e^{100\times 0.5}=e^{50}$. By contrast the total number of conceivable length-$100$ strings is $2^{100}=e^{100\ln 2}=e^{69.3}$.

Step 4. The compression gain. Recording an arbitrary string would need $100\ln 2=69.3$ nats. Recording only which of the $e^{50}$ typical strings occurred needs about $50$ nats. The bias buys a saving of roughly $19$ nats per $100$ symbols.

What this tells us: the typical set holds about $e^{50}$ strings out of $e^{69.3}$ conceivable ones, each typical string has probability about $e^{-50}$, and faithful recording costs about $h=0.5$ nats per symbol rather than the $\ln 2$ a fair coin would demand. Entropy is the exact exponential rate at which both the count of realistic strings and the cost of recording them grow.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $(X,\mathcal{B},\mu ,T)$ is an ergodic measure-preserving system 38.06.02 on a probability space and $P=\{P_1,\dots ,P_k\}$ is a finite measurable partition with $H(P)=-{\sum }_i\mu (P_i)\log \mu (P_i)<\infty$. All logarithms are natural unless a base is named. Write $P^n={\bigvee }_{j=0}^{n-1}{T}^{-j}P$ for the join by the first $n$ symbols of the $P$-itinerary, and for $x\in X$ let $P^n(x)$ denote the atom of $P^n$ containing $x$ (equivalently the cylinder $[x{]}_n$ of points whose first $n$ $P$-labels agree with $x$).

Definition (information function). The information function of the partition $P$ is $$I_P(x)=-\log \mu (P(x))=-\sum _i{1}_{P_i}(x)\log \mu (P_i),$$ the surprise of learning which atom of $P$ contains $x$. Its integral is the partition entropy, ${\int }_X{I}_{P}d\mu =H(P)$. The $n$-block information is $I_{P^n}(x)=-\log \mu (P^n(x))$, with ${\int }_X{I}_{P^n}d\mu =H(P^n)$.

Definition (conditional information). Given a sub-$\sigma$-algebra $\mathcal{A}\subseteq \mathcal{B}$, the conditional information of $P$ given $\mathcal{A}$ is $$I_P(x\mid \mathcal{A})=-\log \mu (P(x)\mid \mathcal{A})(x)=-\sum _i{1}_{P_i}(x)\log \mathbb{E}[1_{P_i}\mid \mathcal{A}](x),$$ where $\mu (P_i\mid \mathcal{A})=\mathbb{E}[1_{P_i}\mid \mathcal{A}]$ is the conditional probability. Its integral is the conditional entropy, ${\int }_X{I}_P(\cdot \mid \mathcal{A})d\mu =H(P\mid \mathcal{A})$. Writing ${\mathcal{P}}_n={\bigvee }_{j=1}^n{T}^{-j}P$ for the $\sigma$-algebra of the next $n$ future symbols and ${\mathcal{P}}_{\infty }={\bigvee }_{j\ge 1}{T}^{-j}P$ for the whole strict future, the limit $f=I_P(\cdot \mid {\mathcal{P}}_{\infty })$ exists and $\int fd\mu =H(P\mid {\mathcal{P}}_{\infty })=h(T,P)$ 38.06.02.

Definition (information cocycle). The $n$-block information telescopes along the chain rule into a sum of conditional informations: $$I_{P^n}(x)=\sum _{j=0}^{n-1}{I}_P\left(T^{j}x\right|{\mathcal{P}}_0^j),{\mathcal{P}}_0^j=\underset{i=1}{\overset{j}{\bigvee }}{T}^{-i}P,$$ so that $I_{P^n}={\sum }_{j=0}^{n-1}{g}_j\circ T^j$ with $g_j=I_P(\cdot \mid {\mathcal{P}}_0^j)$ and $g_j\to f=I_P(\cdot \mid {\mathcal{P}}_{\infty })$ both a.e. and in $L^1$ by the increasing-martingale convergence theorem 37.02.03. This is the information cocycle: an almost-additive functional whose terms approach the single function $f$.

Definition (typical set). For $\epsilon >0$ and $n\ge 1$, the $(n,\epsilon )$-typical set relative to $P$ is $$A_n^{\epsilon }=\{x\in X:|-\frac{1}{n}\log \mu (P^n(x))-h|<\epsilon \},h=h(T,P),$$ the set of points whose length-$n$ name has measure within an exponential factor $e^{\pm n\epsilon }$ of $e^{-nh}$. A generating partition (one with ${\bigvee }_{j\in \mathbb{Z}}{T}^{-j}P=\mathcal{B}\mathrm{mod}\mu$) has $h(T,P)=h(T)$ 38.06.02, so the typical set is then computed with the full Kolmogorov-Sinai entropy.

Counterexamples to common slips Intermediate+

• The information function is random; the entropy is its mean. $I_{P^n}(x)=-\log \mu (P^n(x))$ varies from point to point, while $H(P^n)=\int I_{P^n}d\mu$ is a number. The SMB theorem is the statement that the random normalised information $\frac{1}{n}{I}_{P^n}$ converges to the constant $h$, a far stronger fact than the plain convergence of its mean $\frac{1}{n}H(P^n)\to h$, which holds by definition.

• Ergodicity is essential for a constant limit. Without ergodicity, $\frac{1}{n}{I}_{P^n}(x)\to h(T,P,x)$ converges to an invariant random variable, the local entropy of the ergodic component through $x$, not to a constant. The single number $h$ appears only because ergodicity collapses the invariant $\sigma$-algebra to constants, exactly as in Birkhoff 37.02.03.

• The limit is the conditional, not the unconditional, entropy. The cocycle terms $g_j=I_P(\cdot \mid {\mathcal{P}}_0^j)$ decrease toward $f=I_P(\cdot \mid {\mathcal{P}}_{\infty })$ with $\int f=h(T,P)\le H(P)$, generally strictly less. Reading the limit as $H(P)$ rather than $h(T,P)$ overcounts: the future already determines part of the present symbol.

• Typicality is a measure statement, not a counting statement until you sum. Each typical name has measure about $e^{-nh}$; the count $e^{nh}$ follows only because the typical set has measure near $1$ and the measures are nearly equal. For a non-uniform partition the number of atoms of $P^n$ can be much larger than $e^{nh}$ — most of them are atypical and carry negligible measure.

• SMB is about measure entropy, not topological entropy. The growth rate $e^{nh}$ counts names weighted by $\mu$; the topological entropy counts all distinguishable names regardless of measure and is the supremum over invariant measures 38.06.02. For a non-maximal measure the SMB rate $h_{\mu }$ is strictly below $h_{\mathrm{top}}$.

Key theorem with proof Intermediate+

Theorem (Shannon-McMillan-Breiman; Shannon 1948, McMillan 1953, Breiman 1957). Let $(X,\mathcal{B},\mu ,T)$ be an ergodic measure-preserving system and $P$ a finite partition with $H(P)<\infty$. Then $$-\frac{1}{n}\log \mu (P^n(x))\underset{n\to \infty }{\to }h(T,P)\text{for }\mu \text{-a.e. }x\text{ and in }{L}^1(\mu ).$$ When $P$ generates, the limit is the Kolmogorov-Sinai entropy $h(T)$.

Proof. Decompose the $n$-block information by the chain rule 38.06.02 into the information cocycle $$I_{P^n}(x)=\sum _{j=0}^{n-1}{g}_{n-1-j}(T^{j}x),g_m=I_P(\cdot \mid {\mathcal{P}}_0^m),{\mathcal{P}}_0^m=\underset{i=1}{\overset{m}{\bigvee }}{T}^{-i}P,$$ obtained by writing $I_{P^n}={\sum }_{j=0}^{n-1}{I}_P(T^j\cdot \mid {\bigvee }_{i=1}^{n-1-j}{T}^{-i}P)$ and using $H(R\mid Q)=H(T^{-1}R\mid T^{-1}Q)$ from measure-preservation. The terms satisfy $g_m\downarrow f:=I_P(\cdot \mid {\mathcal{P}}_{\infty })$ a.e. and in $L^1$ by increasing-martingale convergence of the conditional expectations $\mu (P_i\mid {\mathcal{P}}_0^m)\to \mu (P_i\mid {\mathcal{P}}_{\infty })$ 37.02.03, with $\int fd\mu =h(T,P)$.

Split the cocycle into the limit term plus a remainder: $$\frac{1}{n}{I}_{P^n}(x)=\frac{1}{n}\sum _{j=0}^{n-1}f(T^{j}x)+\frac{1}{n}\sum _{j=0}^{n-1}(g_{n-1-j}-f)(T^{j}x).$$ The first average converges by Birkhoff's pointwise theorem 37.02.03 to $\mathbb{E}[f\mid \mathcal{I}]=\int fd\mu =h(T,P)$ a.e. and in $L^1$, using ergodicity to collapse the conditional expectation to the integral. It remains to show the remainder vanishes.

Set $F_N={\sup }_{m\ge N}|g_m-f|$. Since $g_m\to f$ a.e., $F_N\downarrow 0$ a.e.; the maximal inequality below gives $F_0\in L^1$, so dominated convergence yields $\int F_{N}d\mu \to 0$. For the remainder, fix $N$ and bound the terms with $n-1-j\ge N$ by $F_N\circ T^j$ and the finitely many terms with $n-1-j<N$ by $F_0\circ T^j$: $$|\frac{1}{n}\sum _{j=0}^{n-1}(g_{n-1-j}-f)\circ T^j|\le \frac{1}{n}\sum _{j=0}^{n-1}(F_N\circ T^j)+\frac{1}{n}\sum _{j=n-N}^{n-1}(F_0\circ T^j).$$ By Birkhoff the first sum converges a.e. to $\int F_{N}d\mu$, and the second sum has $N$ terms each of which is $o(n)$ along a.e. orbit because $\frac{1}{n}{F}_0(T^{j}x)\to 0$ (a single $L^1$ function visited along a Birkhoff-averaged orbit). Hence ${\mathrm{limsup}}_n|\text{remainder}|\le \int F_{N}d\mu$ a.e., and letting $N\to \infty$ drives the right side to $0$. Therefore $\frac{1}{n}{I}_{P^n}\to h(T,P)$ a.e. The $L^1$ convergence follows from the same domination: $\frac{1}{n}{I}_{P^n}$ is bounded above in $L^1$ by $\frac{1}{n}{\sum }_j{F}_0\circ T^j$, a uniformly integrable family by measure-preservation, so a.e. convergence upgrades to $L^1$.

The needed maximal control is the inequality $${\int }_X\underset{m\ge 0}{\sup }{g}_{m}d\mu \le H(P)+1,$$ which holds because $g^{\ast }={\sup }_m{g}_m$ satisfies the distributional bound $\mu (\{g^{\ast }>\lambda \}\cap P_i)\le e^{-\lambda }$ for each atom $P_i$ (a maximal inequality for the conditional-probability martingale $\mu (P_i\mid {\mathcal{P}}_0^m)$), and integrating the tail $\int g^{\ast }\le {\sum }_i{\int }_{P_i}(1+g^{\ast })d\mu$ via ${\int }_0^{\infty }\mu (g^{\ast }>\lambda )d\lambda$ gives the bound. This dominates every $g_m$ and hence $F_0\le g^{\ast }+f\in L^1$. $\square$

Bridge. The Shannon-McMillan-Breiman theorem builds toward the entire coding-theoretic reading of entropy and appears again in the typical-set and source-coding results of the Advanced section, where the a.e. limit becomes the count $e^{nh}$ of realistic names. The foundational reason the random information $\frac{1}{n}{I}_{P^n}$ converges to the deterministic $h$ is that it is a Birkhoff average of the cocycle whose terms converge to a single function $f$ with mean $h(T,P)$ — this is exactly the marriage of the increasing-martingale convergence $g_m\to f$ from 37.02.03 with the pointwise ergodic theorem applied to $f$. Putting these together, SMB is the dynamical asymptotic equipartition property: it generalises the i.i.d. weak law $-\frac{1}{n}\log p(X_1\cdots X_n)\to H$ of Shannon to arbitrary stationary ergodic sources, and it is dual to the generator theorem of 38.06.02, which certifies that the growth rate $h(T,P)$ this theorem realises pointwise equals the full invariant $h(T)$ whenever $P$ generates. The central insight is that a typical length-$n$ name has measure $e^{-nh}$, so the measure-weighted count of names grows like $e^{nh}$ — the bridge from the abstract entropy of a partition to the concrete combinatorics of compression.

Exercises Intermediate+

Advanced results Master

Theorem 1 (Shannon-McMillan-Breiman; the three modes; Shannon 1948, McMillan 1953, Breiman 1957). For an ergodic system and a finite partition $P$ with $H(P)<\infty$, the normalised information $-\frac{1}{n}\log \mu (P^n(x))$ converges to $h(T,P)$ in three successively stronger senses, matching the three authors. Shannon proved convergence in probability for finite-state Markov sources; McMillan strengthened it to $L^1$ for stationary ergodic sources; Breiman proved the almost-everywhere statement, the individual ergodic theorem of information theory. The generating case gives $h(T)$, so SMB realises the Kolmogorov-Sinai invariant of 38.06.02 as an a.e. pointwise growth rate ^{[Breiman 1957]}.

Theorem 2 (asymptotic equipartition property and typical sets). Fix a generator $P$ and $\epsilon >0$. For all large $n$ the typical set $A_n^{\epsilon }$ has $\mu (A_n^{\epsilon })>1-\epsilon$, each of its names has measure in $(e^{-n(h+\epsilon )},e^{-n(h-\epsilon )})$, and its cardinality satisfies $(1-\epsilon )e^{n(h-\epsilon )}\le |A_n^{\epsilon }|\le e^{n(h+\epsilon )}$. Thus the measure concentrates on $e^{n(h+o(1))}$ nearly-equiprobable names while the remaining $k^n-e^{nh(1+o(1))}$ names are collectively negligible. The AEP is the structural content of SMB, the partition of name-space into a thin high-probability typical set and a vast low-probability remainder ^{[Cover-Thomas 2006]}.

Theorem 3 (Shannon source-coding theorem). The minimal expected per-symbol length of a uniquely decodable binary code for the source $(X,\mu ,T,P)$ converges to $h/\ln 2$ bits as $n\to \infty$: typical names are coded in about $nh/\ln 2$ bits and the atypical remainder costs $o(n)$ on average. No faithful code beats $h$ nats per symbol, and codes approaching it exist; entropy is the exact information rate of the source. This is the operational meaning of measure entropy and the original motivation of Shannon's 1948 theory ^{[Shannon 1948]}.

Theorem 4 (Brin-Katok local entropy formula; Brin-Katok 1983). For an ergodic system on a compact metric space with a continuous $T$, the local entropy at $x$ via dynamical (Bowen) balls $B(x,n,\epsilon )=\{y:d(T^{j}x,T^{j}y)<\epsilon ,0\le j<n\}$ satisfies $$h_{\mu }(T)=\underset{\epsilon \to 0}{\lim }\underset{n}{\mathrm{limsup}}-\frac{1}{n}\log \mu (B(x,n,\epsilon ))=\underset{\epsilon \to 0}{\lim }\underset{n}{\mathrm{liminf}}-\frac{1}{n}\log \mu (B(x,n,\epsilon ))$$ for $\mu$-a.e. $x$. The two limits coincide, giving a partition-free expression of Kolmogorov-Sinai entropy as the exponential decay rate of the measure of $\epsilon$-dynamical balls. This bridges measure entropy to the metric geometry underlying topological entropy and the Katok entropy formula ^{[Brin-Katok 1983]}.

Theorem 5 (Ornstein-Weiss return-time interpretation). For an ergodic generator $P$, the first return time $R_n(x)=\min \{m\ge 1:(T^{m}x{)}_0^{n-1}=x_0^{n-1}\}$ of the length-$n$ name satisfies $\frac{1}{n}\log R_n(x)\to h(T,P)$ a.e. The waiting time to see a given typical name recur is about $e^{nh}$, the reciprocal of its measure $e^{-nh}$ — a return-time shadow of SMB, and the basis of universal entropy estimators (Lempel-Ziv) that learn $h$ from a single orbit without knowing $\mu$ ^{[Cover-Thomas 2006]}.

Synthesis. The five results are one statement read at five resolutions, and the foundational reason they cohere is that the information cocycle $\frac{1}{n}{I}_{P^n}$ is a Birkhoff average whose terms converge to a single function of mean $h$. The AEP is exactly this convergence read as a partition of name-space; source coding is the AEP read as a counting bound, since $e^{nh}$ nearly-equiprobable names need $nh$ nats to label; the Brin-Katok formula is the AEP read geometrically, the cylinder $P^n(x)$ replaced by the dynamical ball $B(x,n,\epsilon )$; and the Ornstein-Weiss law is the AEP read through recurrence, the return time $e^{nh}$ being the reciprocal of the typical measure $e^{-nh}$. Putting these together with 38.06.02, SMB is dual to the generator theorem: the generator theorem certifies that $h(T,P)=h(T)$ as a mean growth rate, and SMB upgrades that to an almost-sure pointwise rate, so the same number $h$ is simultaneously a supremum over partitions, an a.e. information rate, a compression floor, a local volume-decay exponent, and a logarithmic return-time rate. This is exactly the central insight that entropy is one invariant wearing five operational faces, and it generalises Shannon's i.i.d. AEP to every stationary ergodic source — the bridge from the abstract Kolmogorov-Sinai theory to the concrete engineering of data compression.

Full proof set Master

Proposition 1 (the maximal inequality for the information martingale). Let $g^{\ast }={\sup }_{m\ge 0}{I}_P(\cdot \mid {\mathcal{P}}_0^m)$. Then for each atom $P_i$ and each $\lambda >0$, $\mu (\{g^{\ast }>\lambda \}\cap P_i)\le e^{-\lambda }$, and consequently ${\int }_X{g}^{\ast }d\mu \le H(P)+1<\infty$.

Proof. Fix $i$ and let ${\nu }_m=\mu (P_i\mid {\mathcal{P}}_0^m)$, a martingale in $m$ with respect to the filtration $({\mathcal{P}}_0^m)$. The event $\{g^{\ast }>\lambda \}\cap P_i$ requires $-\log {\nu }_m>\lambda$ for some $m$, i.e. ${\nu }_m<e^{-\lambda }$ for some $m$, at a point of $P_i$. Let $\tau$ be the first such $m$ and $E=\{g^{\ast }>\lambda \}\cap P_i$. On $E$ the stopped value ${\nu }_{\tau }<e^{-\lambda }$, and since ${\nu }_m=\mathbb{E}[1_{P_i}\mid {\mathcal{P}}_0^m]$, optional stopping gives $\mu (E)={\int }_E{1}_{P_i}d\mu ={\int }_E{\nu }_{\tau }d\mu \le e^{-\lambda }\mu (\{\tau <\infty \}\cap (\text{restriction}))\le e^{-\lambda }$. Summing the tail, ${\int }_{P_i}{g}^{\ast }d\mu ={\int }_0^{\infty }\mu (\{g^{\ast }>\lambda \}\cap P_i)d\lambda$. Split at ${\lambda }_i=-\log \mu (P_i)$: below ${\lambda }_i$ bound the measure by $\mu (P_i)$, above ${\lambda }_i$ by $e^{-\lambda }$: $${\int }_{P_i}{g}^{\ast }d\mu \le {\lambda }_i\mu (P_i)+{\int }_{{\lambda }_i}^{\infty }{e}^{-\lambda }d\lambda =-\mu (P_i)\log \mu (P_i)+\mu (P_i).$$ Summing over $i$ gives $\int g^{\ast }\le H(P)+1$. $\square$

Proposition 2 (the information cocycle is almost additive). With $g_m=I_P(\cdot \mid {\mathcal{P}}_0^m)$ and $f=I_P(\cdot \mid {\mathcal{P}}_{\infty })$, the $n$-block information satisfies $I_{P^n}={\sum }_{j=0}^{n-1}f\circ T^j+R_n$ where $\frac{1}{n}{R}_n\to 0$ a.e. and in $L^1$.

Proof. By the chain rule (Exercise 3), $I_{P^n}={\sum }_{j=0}^{n-1}{g}_{n-1-j}\circ T^j$. Subtract the additive part: $R_n={\sum }_{j=0}^{n-1}(g_{n-1-j}-f)\circ T^j$. With $F_N={\sup }_{m\ge N}|g_m-f|$, which decreases to $0$ a.e. and lies in $L^1$ since $F_0\le g^{\ast }+f\in L^1$ by Proposition 1, split the sum at the threshold $n-1-j=N$. The terms with $n-1-j\ge N$ are bounded by $F_N\circ T^j$ whose Birkhoff average tends to $\int F_{N}d\mu$, and the $N$ terms with $n-1-j<N$ are bounded by $F_0\circ T^j$, each contributing $o(n)$ along a.e. orbit. Hence ${\mathrm{limsup}}_n\frac{1}{n}|R_n|\le \int F_{N}d\mu$ a.e., and $\int F_{N}d\mu \to 0$ by dominated convergence, so $\frac{1}{n}{R}_n\to 0$ a.e.; the $L^1$ statement follows from uniform integrability of the dominating Birkhoff averages. $\square$

Proposition 3 (SMB pointwise and $L^1$). For an ergodic system, $\frac{1}{n}{I}_{P^n}\to h(T,P)$ a.e. and in $L^1$.

Proof. By Proposition 2, $\frac{1}{n}{I}_{P^n}=\frac{1}{n}{\sum }_{j<n}f\circ T^j+\frac{1}{n}{R}_n$. Birkhoff's theorem 37.02.03 gives $\frac{1}{n}{\sum }_{j<n}f\circ T^j\to \mathbb{E}[f\mid \mathcal{I}]$ a.e. and in $L^1$, and ergodicity makes $\mathcal{I}$ degenerate (every invariant set has measure $0$ or $1$) so the limit is $\int fd\mu =h(T,P)$ 38.06.02. The remainder $\frac{1}{n}{R}_n\to 0$ by Proposition 2. Adding, $\frac{1}{n}{I}_{P^n}\to h(T,P)$ a.e.; the $L^1$ convergence is the sum of the two $L^1$ convergences. $\square$

Proposition 4 (typical-set cardinality bounds). Fix $\epsilon >0$. For all large $n$, $\mu (A_n^{\epsilon })>1-\epsilon$ and $(1-\epsilon )e^{n(h-\epsilon )}\le |A_n^{\epsilon }|\le e^{n(h+\epsilon )}$, where $h=h(T,P)$ and names are atoms of $P^n$.

Proof. By Proposition 3 and Egorov, $-\frac{1}{n}\log \mu (P^n(x))\to h$ in measure, so $\mu (A_n^{\epsilon })\to 1$; pick $n$ with $\mu (A_n^{\epsilon })>1-\epsilon$. For $x\in A_n^{\epsilon }$ the defining inequality gives $e^{-n(h+\epsilon )}<\mu (P^n(x))<e^{-n(h-\epsilon )}$. The atoms in $A_n^{\epsilon }$ are disjoint with total measure $\mu (A_n^{\epsilon })\le 1$, so the lower bound on each measure forces $|A_n^{\epsilon }|e^{-n(h+\epsilon )}\le 1$, i.e. $|A_n^{\epsilon }|\le e^{n(h+\epsilon )}$. The total measure exceeds $1-\epsilon$ and each atom has measure below $e^{-n(h-\epsilon )}$, so $|A_n^{\epsilon }|e^{-n(h-\epsilon )}\ge 1-\epsilon$, i.e. $|A_n^{\epsilon }|\ge (1-\epsilon )e^{n(h-\epsilon )}$. $\square$

Connections Master

• The Kolmogorov-Sinai entropy and generator theorem 38.06.02 is the direct parent: SMB realises the invariant $h(T)={\sup }_{P}h(T,P)$ as an almost-sure pointwise growth rate, and the generator theorem is exactly what lets the partition-relative limit $h(T,P)$ in SMB be read as the full entropy $h(T)$. The conditional-entropy chain rule and the join structure of that unit supply the information cocycle whose convergence is the whole proof.

• The ergodic theorems of Birkhoff, von Neumann, and Kingman 37.02.03 are the analytic engine: Birkhoff's pointwise theorem converts the limiting cocycle term $f$ into the constant $h$, and the increasing-martingale convergence theorem (the conditional-expectation half of that unit) drives the cocycle terms $g_m\to f$. SMB is precisely the composition of these two convergence theorems applied to the information function.

• The strong law of large numbers 37.02.02 is the i.i.d. special case: for a Bernoulli source the information cocycle is a genuine sum of i.i.d. terms $I_P\circ T^j$ and SMB collapses to Shannon's original AEP $-\frac{1}{n}\log p(X_1\cdots X_n)\to H$, the strong law applied to the per-symbol surprise.

• The Oseledets multiplicative ergodic theorem and Lyapunov exponents 38.07.01 share the cocycle architecture: both extract an a.e. exponential rate from a stationary system, SMB from the additive information cocycle and Oseledets from the multiplicative matrix cocycle, and in smooth systems the Pesin formula ties the SMB entropy rate to the sum of positive Oseledets exponents.

• The hyperbolic-sets and Smale decomposition theory 38.03.01 is where the Brin-Katok local-entropy formula becomes geometric: on a hyperbolic set the dynamical balls $B(x,n,\epsilon )$ are aligned with the stable-unstable splitting, so the measure-decay rate of SMB equals the unstable expansion rate, recovering the entropy $=\log \lambda$ of an Anosov system through the Bowen-ball picture.

Historical & philosophical context Master

The theorem grew directly from Claude Shannon's 1948 founding paper of information theory ^{[Shannon 1948]}, where the quantity $-\sum p_i\log p_i$ was introduced as the entropy of a source and the asymptotic equipartition property was proved, in the form of convergence in probability, for finite-state Markov chains. Shannon's argument was tailored to the Markov setting and used the law of large numbers on the per-symbol log-probabilities. Brockway McMillan's 1953 paper in the Annals of Mathematical Statistics ^{[McMillan 1953]} recast the result for arbitrary stationary ergodic sources and strengthened the conclusion to $L^1$ convergence, introducing the measure-theoretic framing that connected information theory to ergodic theory; the result is sometimes called the McMillan theorem in the $L^1$ form.

Leo Breiman's 1957 note, again in the Annals ^{[Breiman 1957]}, proved the almost-everywhere version — the individual, or pointwise, ergodic theorem of information theory — completing the trio of names. Breiman's argument is the martingale-and-maximal-inequality proof reproduced in the modern literature: the information cocycle, the increasing-martingale convergence of the conditional probabilities, and a maximal inequality controlling the supremum of the conditional informations in $L^1$. A correction to Breiman's original maximal-inequality step was published shortly after, and the corrected argument became standard in Billingsley's and later Walters's textbook treatments.

The partition-free local form was given by Michael Brin and Anatole Katok in 1983 ^{[Brin-Katok 1983]}, who showed that the measure of a dynamical $\epsilon$-ball decays at the rate of the Kolmogorov-Sinai entropy, tying the SMB growth rate to the metric geometry that underlies topological entropy. The information-theoretic descendants — the Lempel-Ziv universal compression algorithms and the Ornstein-Weiss return-time estimators — turned the theorem into the practical statement that a single long sample reveals the source's entropy, which is the foundation of modern lossless compression ^{[Cover-Thomas 2006]}.

Bibliography Master

@article{Shannon1948,
  author  = {Shannon, Claude E.},
  title   = {A mathematical theory of communication},
  journal = {Bell System Technical Journal},
  volume  = {27},
  year    = {1948},
  pages   = {379--423, 623--656}
}

@article{McMillan1953,
  author  = {McMillan, Brockway},
  title   = {The basic theorems of information theory},
  journal = {Annals of Mathematical Statistics},
  volume  = {24},
  number  = {2},
  year    = {1953},
  pages   = {196--219}
}

@article{Breiman1957,
  author  = {Breiman, Leo},
  title   = {The individual ergodic theorem of information theory},
  journal = {Annals of Mathematical Statistics},
  volume  = {28},
  number  = {3},
  year    = {1957},
  pages   = {809--811}
}

@incollection{BrinKatok1983,
  author    = {Brin, Michael and Katok, Anatole},
  title     = {On local entropy},
  booktitle = {Geometric Dynamics},
  series    = {Lecture Notes in Mathematics},
  volume    = {1007},
  publisher = {Springer},
  year      = {1983},
  pages     = {30--38}
}

@book{Walters1982,
  author    = {Walters, Peter},
  title     = {An Introduction to Ergodic Theory},
  publisher = {Springer},
  series    = {Graduate Texts in Mathematics},
  volume    = {79},
  year      = {1982}
}

@book{Petersen1983,
  author    = {Petersen, Karl},
  title     = {Ergodic Theory},
  publisher = {Cambridge University Press},
  year      = {1983}
}

@book{Shields1996,
  author    = {Shields, Paul C.},
  title     = {The Ergodic Theory of Discrete Sample Paths},
  publisher = {American Mathematical Society},
  series    = {Graduate Studies in Mathematics},
  volume    = {13},
  year      = {1996}
}

@book{CoverThomas2006,
  author    = {Cover, Thomas M. and Thomas, Joy A.},
  title     = {Elements of Information Theory},
  edition   = {2},
  publisher = {Wiley},
  year      = {2006}
}