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.

The n-letter mutual information of a DMC is at most nC

Statement

For every input probability vector on $X^{n}$ and output $Y^{n}$ generated by a finite DMC $W^{n}$ , one has $I (X^{n}; Y^{n}) \leq n C (W)$ .

Facts & Assumptions

Given: A finite DMC $W$ , $n \geq 1$ , and any probability vector for the input word $X^{n}$ .

[F1]

Finite entropy and mutual-information chain rules: $I (U; V) = H (V) - H (V ∣ U)$ and conditional entropy has its finite chain rule.

[F2]

Finite conditional mutual information identities and equality: finite conditional mutual information is nonnegative; in particular, conditioning on a finite variable cannot increase conditional entropy.

[F3]

Finite discrete memoryless channels and The DMC product laws are stochastic kernels: $P (Y^{n} = y^{n} ∣ X^{n} = x^{n}) = \prod_{i = 1}^{n} W (y_{i} ∣ x_{i})$ .

[F4]

Single-letter information capacity of a finite DMC: $I (X_{i}; Y_{i}) \leq C (W)$ for every marginal input law of $X_{i}$ .

Proof

1.1F1F2givenalgebra

By [F1], $H (Y^{n}) = \sum_{i = 1}^{n} H (Y_{i} ∣ Y^{i - 1})$ . For each $i$ , [F2] gives $H (Y_{i} ∣ Y^{i - 1}) \leq H (Y_{i})$ , so $H (Y^{n}) \leq \sum_{i} H (Y_{i})$ .

1.2F1F3givenalgebra

The conditional chain rule in [F1] gives $H (Y^{n} ∣ X^{n}) = \sum_{i} H (Y_{i} ∣ X^{n}, Y^{i - 1})$ . For every positive-probability value $(x^{n}, y^{i - 1})$ , factorization [F3] and summing the unused future coordinates show that the conditional law of $Y_{i}$ is $W (\cdot ∣ x_{i})$ . Thus $H (Y_{i} ∣ X^{n}, Y^{i - 1}) = H (Y_{i} ∣ X_{i})$ , including after averaging over conditioning values.

2.1F1F4step 1.1step 1.2algebra∎

By [F1], $I (X^{n}; Y^{n}) = H (Y^{n}) - H (Y^{n} ∣ X^{n})$ . Steps 1.1 and 1.2 therefore give $I (X^{n}; Y^{n}) \leq \sum_{i = 1}^{n} (H (Y_{i}) - H (Y_{i} ∣ X_{i})) = \sum_{i = 1}^{n} I (X_{i}; Y_{i}) \leq n C (W)$ by [F4].

Depends on

Used by

Dependency tree · two levels

18 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 19 §19.1 (standard reference, not scraped)
Robert Gallager, Principles of Digital Communication I, Chapter 8 §§8.7.2, MIT OpenCourseWare (standard reference, not scraped)