DefinitionDefinition: AI-adaptedProof: AI-generatedPipeline-generatedprecheck pending

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.

Finite-alphabet stationary source

Definition

Consider a finite nonempty alphabet $A$ , a probability measure $P$ on $A^{Z}$ , and the left shift $T (x)_{j} = x_{j + 1}$ .

The shift is measurable on the product sigma-algebra. Call $P$ stationary when it is measure preserving under this shift, precisely the condition in Measure-preserving transformations and systems.

For a stationary $P$ , call the source ergodic when each event $E$ satisfying $T^{- 1} E = E$ has $P (E) \in {0, 1}$ ; by Ergodicity relative to an invariant measure this is exactly ergodicity of the probability system.

Facts & Assumptions

Given: A finite nonempty alphabet $A$ , a probability measure $P$ on $A^{Z}$ , and the left shift $T (x)_{j} = x_{j + 1}$ .

[F1]

Measure-preserving transformations and systems: $T$ preserves $P$ exactly when $P (T^{- 1} E) = P (E)$ for each measurable event $E$ .

[F2]

Ergodicity relative to an invariant measure: a probability-preserving system is ergodic when each strictly invariant event has probability zero or one.

Proof

Given: The objects in the statement and the conventions [F1]–[F2].

1.1givenF1algebra

A basic product cylinder restricts only finitely many coordinates. Its inverse image under $T$ imposes the same restrictions on the coordinates shifted by one, so is again a product cylinder and is measurable. Since product cylinders generate the product sigma-algebra and inverse image preserves complements and countable unions, $T$ is measurable on that sigma-algebra. Call $P$ stationary when it is measure preserving under this measurable shift, precisely the condition in [F1].

2.1F2step 1.1algebra∎

For a stationary $P$ , call the source ergodic when each event $E$ satisfying $T^{- 1} E = E$ has $P (E) \in {0, 1}$ ; by [F2] this is exactly ergodicity of the probability system.

Depends on

Used by

Finite-block LZ78 incremental prefix code Algorithm
Asymptotically mean stationary sources Definition
Finite-past information densities Definition
Finite-state compressibility of an individual sequence Definition
Fixed-length lossless block codes and error probability Definition
Information rate of a general finite-alphabet process Definition
LZ77 previous-match length and recurrence time Definition
Stationary finite-block information rate-distortion function Definition
IID and two-state Markov entropy rates Example
Conditional block information rate given the infinite past Lemma
Convergence and integrable envelope for finite-past information Lemma
Random-cut stationary ergodic block-channel approximation Lemma
Componentwise Shannon–McMillan–Breiman theorem Theorem
Entropy-rate limit for a stationary finite-alphabet source Theorem
Stationary-ergodic bounded-distortion rate-distortion theorem Theorem

Dependency tree · two levels

5 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)