TheoremStatement: 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.

Strong converse for finite-alphabet DMCs

Statement

Let $W$ be a finite DMC with finite nonempty input and output alphabets and no input-cost constraint. For any sequence of length- $n$ codes with ${lim inf}_{n \to \infty} n^{- 1} \ln M_{n} > C (W)$ , the average success probability tends to zero; hence both average and maximal error tend to one.

Facts & Assumptions

Given: A finite DMC $W$ and a sequence of deterministic length- $n$ codes with $M_{n}$ messages.

[F1]

Finite DMC information capacity is attained and Capacity-achieving output laws bound every row divergence: a maximizing input law $P_{X}^{*}$ exists, and for $Q^{*} : = P_{X}^{*} W$ every row is supported on $Q^{*}$ with $D (W (\cdot ∣ x) ∥ Q^{*}) \leq C (W)$ .

[F2]

Uniform concentration around the capacity output divergence bound: for every fixed $η > 0$ , uniformly over input words $x^{n}$ , the probability under $W^{n} (\cdot ∣ x^{n})$ that $\ln (W^{n} (Y^{n} ∣ x^{n}) / (Q^{*})^{n} (Y^{n})) > n (C (W) + η)$ is at most $V / (n η^{2})$ .

[F3]

Fixed-length codes for a finite DMC and Average and maximal error of a fixed-length code: the decoder regions $D_{m} : = {y^{n} : d (y^{n}) = m}$ are pairwise disjoint, and average success is $M_{n}^{- 1} \sum_{m} W^{n} (D_{m} ∣ e (m))$ .

Proof

1.1F1F2F3givenalgebra

By [F1] choose a maximizing input law $P_{X}^{*}$ and set $Q^{*} : = P_{X}^{*} W$ . Fix a blocklength $n$ , a codeword $x_{m}^{n} = e (m)$ , and a threshold $τ$ . Split $D_{m}$ within the support of $W^{n} (\cdot ∣ x_{m}^{n})$ into outputs where $\ln (W^{n} (y^{n} ∣ x_{m}^{n}) / (Q^{*})^{n} (y^{n})) > τ$ and the supported complement. The first part has channel probability at most the threshold-tail probability in [F2]. On the supported complement, $W^{n} (y^{n} ∣ x_{m}^{n}) \leq e^{τ} (Q^{*})^{n} (y^{n})$ by the likelihood ratio; outside the support, $W^{n} (y^{n} ∣ x_{m}^{n}) = 0$ , so the same inequality holds there. Hence the remaining channel probability is at most $e^{τ} (Q^{*})^{n} (D_{m})$ .

2.1F2F3step 1.1algebra

Average the bound in step 1.1 over messages. The tail term is at most $V / (n η^{2})$ uniformly by [F2]. Pairwise disjointness from [F3] gives $\sum_{m} (Q^{*})^{n} (D_{m}) \leq 1$ , so average success is at most $V / (n η^{2}) + e^{τ} / M_{n}$ .

3.1F3step 2.1givenchoosealgebra∎

Choose $η > 0$ such that eventually $n^{- 1} \ln M_{n} \geq C (W) + 2 η$ , which is possible by the strict liminf hypothesis. Set $τ = n (C (W) + η)$ . Then $e^{τ} / M_{n} \leq e^{- n η}$ , and step 2.1 bounds success by $V / (n η^{2}) + e^{- n η} \to 0$ . Thus average error tends to one. Since maximal error is at least average error, it too tends to one.

Depends on

Used by

The error exponent is zero above finite-DMC capacity Theorem

Dependency tree · two levels

22 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 capacity (standard reference, not scraped)