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.

Expected lossless prefix-code rate for stationary sources

Statement

For every stationary finite-alphabet source, the optimal expected prefix-code length for X^n divided by n converges to the entropy rate.

Facts & Assumptions

Given: A stationary finite-alphabet source, its length- $n$ block entropy $H_{n}$ , and the infimum $L_{n}^{*}$ of expected lengths among binary prefix codes describing one known length- $n$ block on its positive-probability support.

[F1]

Finite-block information and entropy in bits: $H_{n}$ is the entropy of the finite block law.

[F2]

Entropy lower and Shannon upper bounds for finite prefix codes: for every finite source, $H_{n} \leq L_{n}^{*} < H_{n} + 1$ bit.

[F3]

Entropy-rate limit for a stationary finite-alphabet source: $H_{n} / n \to h$ .

Proof

Given: The source, code class and entropy conventions [F1]–[F3].

1.1F1F2given

Apply [F2] to each finite block law: $H_{n} \leq L_{n}^{*} < H_{n} + 1$ . The lower bound includes every finite prefix code; the upper bound is attained within one bit by a Shannon code on the positive-probability support.

2.1F2F3step 1.1algebra

Divide by $n$ and use [F3]. Since $1 / n \to 0$ , both bounds converge to $h$ , so $L_{n}^{*} / n \to h$ . No ergodicity is needed because the argument uses only stationary block entropies.

3.1F1F2step 2.1algebra∎

If the source is deterministic, then $H_{n} = 0$ and the sole positive-probability block can be assigned the empty codeword; the rate is zero. For all other cases the same one-bit additive bound applies.

Depends on

Used by

LZ78 expected-rate universality for stationary sources Theorem

Dependency tree · two levels

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