LemmaStatement: Literature-sourcedProof: AI-generatedPipeline-generatedprecheck pass

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 iid log-likelihood averages concentrate

Statement

Let $P = (p_{x})$ and $Q = (q_{x})$ be probability vectors on a finite nonempty alphabet with $P ≪ Q$ . For $n \geq 1$ , write $P^{n} (x_{1}, \dots, x_{n}) = \prod_{i} p_{x_{i}}$ and $Q^{n} (x_{1}, \dots, x_{n}) = \prod_{i} q_{x_{i}}$ . Let $X_{1}, \dots, X_{n}$ be independent with common law $P$ , define $ℓ (x) = \log (p_{x} / q_{x})$ when $p_{x} > 0$ and $ℓ (x) = 0$ when $p_{x} = 0$ , and put $L_{n} = \sum_{i = 1}^{n} ℓ (X_{i})$ . Then $L_{n} / n \to D (P ∥ Q)$ in probability as $n \to \infty$ . For every $x^{n} \in supp (P)^{n}$ , one also has $Q^{n} (x^{n}) = P^{n} (x^{n}) \exp (- L_{n} (x^{n}))$ .

Facts & Assumptions

Given: $P, Q$ with $P ≪ Q$ , and an independent identically distributed sample $X_{1}, \dots, X_{n}$ with law $P$ .

[F1]

Finite probability vectors: $supp P$ is finite and all its coordinates have positive mass; $P ≪ Q$ gives $q_{x} > 0$ whenever $p_{x} > 0$ .

[F2]

Finite Kullback–Leibler divergence: the finite mean of $ℓ (X) = \log (p_{X} / q_{X})$ under $P$ is $\sum_{x : p_{x} > 0} p_{x} \log (p_{x} / q_{x}) = D (P ∥ Q)$ .

[F3]

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: the logarithm of a finite product of positive ratios is the sum of their logarithms.

[F4]

The natural logarithm as the inverse of the exponential function: $\exp (\log r) = r$ for $r > 0$ .

[F5]

The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ : $\exp (- u) = 1 / \exp (u)$ for every real $u$ .

[F6]

Expectation of a real random variable on a finite probability space: on a finite probability space, expectation is the finite probability-weighted sum.

Proof

1.1F1F3F4F5givenalgebra

For $x^{n} \in supp (P)^{n}$ , every ratio $p_{x_{i}} / q_{x_{i}}$ is positive. By [F3], $L_{n} (x^{n}) = \log \prod_{i} (p_{x_{i}} / q_{x_{i}})$ . Applying [F4] and [F5] gives $\exp (L_{n} (x^{n})) = P^{n} (x^{n}) / Q^{n} (x^{n})$ and hence $Q^{n} (x^{n}) = P^{n} (x^{n}) \exp (- L_{n} (x^{n}))$ .

2.1F1F2F6givenalgebra∎

The values $ℓ (x)$ on the finite set $supp P$ form a bounded finite-valued random variable. Put $Y_{i} : = ℓ (X_{i}) - D (P ∥ Q)$ ; [F2] and the finite-sum expectation formula [F6] give $E [Y_{i}] = 0$ . Let $σ^{2} = E [Y_{i}^{2}] < \infty$ , which is independent of $i$ since all $X_{i}$ have law $P$ . For $i \neq j$ , expanding the expectation on the product law $P^{n}$ using [F6] gives $E [Y_{i} Y_{j}] = {(\sum_{x} p_{x} (ℓ (x) - D (P ∥ Q)))}^{2} \prod_{k \neq i, j} (\sum_{x} p_{x}) = 0,$ where the square is zero by [F2] and the remaining factors equal one by [F1]. Expanding $E [(n^{- 1} \sum_{i} Y_{i})^{2}]$ therefore gives $σ^{2} / n$ . For every $δ > 0$ , the pointwise inequality $δ^{2} 1_{{∣ n^{- 1} \sum_{i} Y_{i} ∣ \geq δ}} \leq (n^{- 1} \sum_{i} Y_{i})^{2}$ and [F6] imply $P^{n} (∣ L_{n} / n - D (P ∥ Q) ∣ \geq δ) \leq σ^{2} / (n δ^{2}) \to 0$ , since the expectation of an indicator is the probability of its event.

Depends on

Used by

KL is the iid type-II testing exponent Theorem

Dependency tree · two levels

16 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

Yury Polyanskiy and Yihong Wu, Information Theory: From Coding to Learning, Chapter 14, §14.5, proof of Theorem 14.13 (standard reference, not scraped)