CorollaryStatement: AI-adaptedProof: AI-generatedPipeline-generatedprecheck pendingjudge pass (gpt-6-luna)

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.

Fano bound for erasure and out-of-alphabet estimates

Statement

Let $X$ have a finite alphabet $X$ of size $m \geq 1$ , let $Y$ be finite, and let $\hat{X}$ be any finite estimate output generated from $Y$ , with an output alphabet that may contain symbols outside $X$ . Assume $X \to Y \to \hat{X}$ , and set $P_{e} = P [\hat{X} \neq X]$ . Use $h_{2}$ as defined in Finite-alphabet Fano inequality. Then

$H (X ∣ Y) \leq h_{2} (P_{e}) + P_{e} \ln m .$

If $X$ is uniform on $X$ , then

$(1 - P_{e}) \ln m \leq I (X; Y) + h_{2} (P_{e}) .$

Facts & Assumptions

Given: A finite joint pmf with $p_{X Y \hat{X}} = p_{X Y} p_{\hat{X} ∣ Y}$ , finite $X$ of size $m \geq 1$ , and an arbitrary finite estimate alphabet.

[F1]

Finite-alphabet Fano inequality: $h_{2} (t) = - t \ln t - (1 - t) \ln (1 - t)$ with $0 \ln 0 = 0$ .

[F2]

Data processing for a finite Markov chain, with equality condition: for $X \to Y \to \hat{X}$ , $I (X; \hat{X}) \leq I (X; Y)$ .

[F3]

Finite entropy and mutual-information chain rules: $I (X; Y) = H (X) - H (X ∣ Y)$ and finite conditional entropy satisfies the chain rule.

[F4]

Finite KL divergence is nonnegative with equality exactly at equal laws: finite KL divergence is nonnegative.

[F5]

Finite mutual information: $I (X; Y) = D (p_{X Y} ∥ p_{X} \otimes p_{Y})$ .

[F6]

Finite distributions, entropy, divergence, and stochastic matrices: $H (p) = - \sum_{p_{i} > 0} p_{i} \ln p_{i}$ .

[F7]

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: $\ln$ is increasing and $\ln 1 = 0$ .

Proof

1.1givenF2F3F5F7casesalgebra

If $m = 1$ , then $X$ is constant, so $H (X ∣ Y) = 0$ and $I (X; Y) = 0$ because $p_{X Y} = p_{X} \otimes p_{Y}$ ; also $h_{2} (P_{e}) \geq 0$ since $\ln t \leq 0$ for $0 < t \leq 1$ by [F7], with the zero term set to $0$ . Thus both claims hold. Assume $m \geq 2$ below. From [F2] and [F3], $H (X ∣ Y) \leq H (X ∣ \hat{X})$ .

1.2F1F3F4F5F6givenalgebra

Define $E = 1 {X \neq \hat{X}}$ . It is determined by $(X, \hat{X})$ , so [F3]'s entropy chain rule gives $H (X ∣ \hat{X}) = H (E ∣ \hat{X}) + H (X ∣ E, \hat{X})$ . Also $H (E) = h_{2} (P_{e})$ by [F1] and [F6]. The finite MI identity [F3] gives $H (E ∣ \hat{X}) = H (E) - I (E; \hat{X})$ , and [F4]–[F5] make this MI nonnegative, so $H (E ∣ \hat{X}) \leq h_{2} (P_{e})$ .

2.1F4F6step 1.2givenalgebra

On $E = 0$ , $X = \hat{X}$ and the conditional entropy is zero. On $E = 1$ , for each fixed estimator output the message $X$ has at most $m$ possible values. Any pmf $r$ on at most $m$ points has $H (r) \leq \ln m$ : pad it by zeros to $m$ coordinates and compare with the uniform pmf $u_{m}$ ; [F4] gives $0 \leq D (r ∥ u_{m}) = \ln m - H (r)$ by [F6]. Averaging the two branches yields $H (X ∣ E, \hat{X}) \leq P_{e} \ln m$ .

3.1F1F3F6step 1.1step 1.2step 2.1algebra∎

Combining steps 1.1, 1.2, and 2.1 proves $H (X ∣ Y) \leq h_{2} (P_{e}) + P_{e} \ln m$ . For uniform $X$ , [F6] gives $H (X) = \ln m$ ; subtracting the conditional-entropy bound from $H (X)$ and using [F3] gives $(1 - P_{e}) \ln m \leq I (X; Y) + h_{2} (P_{e})$ . The formulas remain valid for $P_{e} = 0$ or $1$ because zero-probability branches are omitted and [F1] fixes the endpoints of $h_{2}$ .

Depends on

Used by

Strong-secrecy capacity of a finite DMC wiretap channel 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, author prepublication (standard reference, not scraped)
Robert M. Gray, Entropy and Information Theory, corrected first edition (standard reference, not scraped)