LemmaStatement: Literature-sourcedProof: 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.

Uniform concentration around the capacity output divergence bound

Statement

Let $P_{X}^{*}$ attain $C (W)$ and $Q^{*} = P_{X}^{*} W$ . There is a finite constant $V \geq 0$ such that, for every $n \geq 1$ , every $x^{n} \in X^{n}$ , and every $δ > 0$ , under output law $W^{n} (\cdot ∣ x^{n})$ , $\Pr [\ln \frac{W^{n} (Y^{n} ∣ x^{n})}{(Q^{*})^{n} (Y^{n})} > n (C (W) + δ)] \leq \frac{V}{n δ^{2}} .$ The likelihood ratio is evaluated only on the support of $W^{n} (\cdot ∣ x^{n})$ .

Facts & Assumptions

Given: A finite DMC $W$ , a capacity-achieving input law $P_{X}^{*}$ , and the associated output law $Q^{*}$ .

[F1]

Capacity-achieving output laws bound every row divergence: every row $W (\cdot ∣ x)$ is supported on $Q^{*}$ and has mean log likelihood ratio $D (W (\cdot ∣ x) ∥ Q^{*}) \leq C (W)$ .

[F2]

Finite Kullback–Leibler divergence and The natural logarithm as the inverse of the exponential function: the row divergence uses the natural-log likelihood ratio $\ln (W (y ∣ x) / Q^{*} (y))$ , evaluated only where $W (y ∣ x) > 0$ .

[F3]

Finite discrete memoryless channels and The DMC product laws are stochastic kernels: conditional on a fixed input word, the output law is the product of the corresponding row laws.

Proof

1.1F1F2given

For each $x \in X$ , the random variable $Z_{x} : = \ln (W (Y ∣ x) / Q^{*} (Y))$ under row law $W (\cdot ∣ x)$ is finite on its support by [F1]. Its mean is $D (W (\cdot ∣ x) ∥ Q^{*}) \leq C (W)$ , and it has finite variance because it takes only finitely many values. Thus $V : = \max_{x \in X} Var (Z_{x})$ is finite.

2.1F1F2F3step 1.1algebra∎

Fix $x^{n}$ . By [F3], the coordinate log likelihoods are independent. Their sum $S_{n}$ therefore has mean at most $n C (W)$ and variance at most $n V$ . On the event $S_{n} > n (C (W) + δ)$ one has $∣ S_{n} - E S_{n} ∣ > n δ$ , so the squared deviation is at least $n^{2} δ^{2}$ . Taking expectations bounds the event probability by $E [(S_{n} - E S_{n})^{2}] / (n^{2} δ^{2}) \leq V / (n δ^{2})$ .

Depends on

Used by

Strong converse for finite-alphabet DMCs Theorem

Dependency tree · two levels

20 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 22 §22.1 (standard reference, not scraped)
MIT 6.441 Information Theory, Lecture 8, maximizing DMC capacity (standard reference, not scraped)