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.

Information rate of a general finite-alphabet process

Definition

Consider a finite alphabet $A$ and a process law $P$ on $A^{N_{0}}$ ; $H_{n} : = H (X_{0}^{n - 1})$ is as in Finite-block information and entropy in bits.

Define the upper information rate $\overline{h} (P) : = {lim sup}_{n \to \infty} H_{n} / n$ and, when the limsup and liminf agree, the information rate $h (P) : = \lim_{n \to \infty} H_{n} / n$ . This definition does not assume stationarity.

Since $X_{0}^{n - 1}$ has at most $∣ A ∣^{n}$ values, $0 \leq H_{n} \leq n \log_{2} ∣ A ∣$ ; consequently the upper information rate is defined and lies in $[0, \log_{2} ∣ A ∣]$ , and whenever the information-rate limit exists it lies in the same interval.

Facts & Assumptions

Given: A finite alphabet $A$ and a process law $P$ on $A^{N_{0}}$ ; $H_{n} : = H (X_{0}^{n - 1})$ is as in Finite-block information and entropy in bits.

[F1]

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

[F2]

Finite KL nonnegativity for subprobability references: for a finite probability law $p$ and a positive reference probability law $q$ , $\sum_{x : p (x) > 0} p (x) \log_{2} (p (x) / q (x)) \geq 0$ .

Proof

Given: The process and finite-block entropy [F1].

1.1F1givenalgebra

2.1F1F2givenstep 1.1algebra∎

Every positive block probability is at most one, so the finite-sum formula in [F1] gives $H_{n} \geq 0$ . Let $N = ∣ A ∣^{n}$ and compare the block law $p_{n}$ with the uniform law $q (x) = 1 / N$ on the nonempty finite set $A^{n}$ . By [F2], $0 \leq \sum_{x : p_{n} (x) > 0} p_{n} (x) \log_{2} \frac{p_{n} (x)}{q (x)} = - H_{n} + \log_{2} N .$ Hence $H_{n} \leq \log_{2} N = n \log_{2} ∣ A ∣$ . Consequently the upper information rate is defined and lies in $[0, \log_{2} ∣ A ∣]$ , and whenever the information-rate limit exists it lies in the same interval.

Depends on

Used by

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)