TheoremStatement: AI-adaptedProof: AI-generatedPipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Componentwise Shannon–McMillan–Breiman theorem

Statement

For every stationary finite-alphabet source, proves -n^{-1}log_2 P(X_0^{n-1}) converges almost surely and in L1 to the invariant Birkhoff limit of infinite-past information density, with mean equal to the entropy rate in bits.

Facts & Assumptions

Given: A stationary finite-alphabet source $X$ over $A$ , entropy rate $h$ , and $g_{k}, g_{\infty}$ from Finite-past information densities.

[F1]

Convergence and integrable envelope for finite-past information: $g_{k} \to g_{\infty}$ almost surely, $g_{\infty} \in L^{1}$ , and $E g_{\infty} = h$ .

[F2]

Triangular averages of finite-past information converge to the infinite-past average: under the integrable envelope, $n^{- 1} \sum_{i < n} g_{i} (T^{i} x)$ and $n^{- 1} \sum_{i < n} g_{\infty} (T^{i} x)$ have the same almost-sure limit.

[F3]

Birkhoff pointwise ergodic theorem: time averages of $g_{\infty}$ converge almost surely to an invariant integrable limit.

[F4]

Ergodic averages converge in Lp on finite-measure spaces: those averages converge in $L^{1}$ on the probability space.

Proof

Given: The source and [F1]–[F4].

1.1F1givenalgebra

The chain rule for finite block probabilities gives, almost surely, $- \log_{2} P (X_{0}^{n - 1}) = \sum_{i = 0}^{n - 1} - \log_{2} P (X_{i} ∣ X_{0}^{i - 1}) = \sum_{i = 0}^{n - 1} g_{i} (T^{i} X) .$ The equality holds on positive-probability blocks; their complement has probability zero.

2.1F1F2F3F4step 1.1

By [F3]–[F4], $A_{n} g_{\infty} = n^{- 1} \sum_{i < n} g_{\infty} (T^{i} X)$ converges almost surely and in $L^{1}$ to an invariant random variable $G^{*}$ . By [F2] and step 1.1, the difference between $- n^{- 1} \log_{2} P (X_{0}^{n - 1})$ and $A_{n} g_{\infty}$ tends to zero almost surely and in $L^{1}$ . This proves both asserted modes of convergence.

3.1F1F4step 2.1algebra∎

The $L^{1}$ convergence [F4] implies $E G^{*} = E g_{\infty} = h$ ; the limit is therefore finite and has mean equal to the stationary entropy rate. It need not be constant without ergodicity.

Depends on

Used by

Ergodic Shannon–McMillan–Breiman theorem Corollary
Invariant conditional-entropy description of the SMB limit Corollary

Dependency tree · two levels

32 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Robert M. Gray, Entropy and Information Theory, corrected edition (standard reference, not scraped)