46.03.03 · information-theory / 03-channel-capacity

Fano's Inequality and the Converse to the Channel Coding Theorem

shipped3 tiersLean: none

Anchor (Master): Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §2.8, §7.4-7.7; Csiszar & Korner 2011 Information Theory 2e (Cambridge) §1.2-1.3; Fano 1961 Transmission of Information (MIT Press) Ch. 4-5

Intuition Beginner

Suppose I think of a number between 1 and 100, and you get to ask me yes/no questions to figure it out. If I answer each question truthfully, you need about 7 questions (since $2^{7} = 128 > 100$ ). That is because the entropy is about 7 bits.

Now suppose I answer each question correctly with probability 0.9, and with probability 0.1 I lie. How well can you guess my number now? Sometimes my answers will mislead you, and your guess will be wrong.

Fano's inequality quantifies this. It says: if the probability of guessing wrong is $P_{e}$ , then the conditional entropy of my number given your information satisfies $H (X ∣ Y) \leq H (P_{e}) + P_{e} \times lo g (99)$ . The first term, $H (P_{e})$ , is the uncertainty about whether you guessed right. The second term, $P_{e} \times lo g (99)$ , is the remaining uncertainty about what the number actually is, weighted by how often you are wrong.

When $P_{e}$ is small (you guess right most of the time), the conditional entropy is small: $Y$ tells you a lot about $X$ . When $P_{e}$ is close to 1 (you are usually wrong), the conditional entropy is large: $Y$ does not help much.

The converse to the channel coding theorem uses Fano's inequality to prove that you cannot transmit information faster than the channel capacity $C$ . If you try to send $R > C$ bits per channel use, the decoder's error probability cannot go to zero, because Fano's inequality forces a contradiction: the rate would require more mutual information than the channel provides.

Fano's inequality has a converse direction too: if the conditional entropy $H (X ∣ Y)$ is large, then the error probability must be large. Together, these two directions say that conditional entropy and error probability control each other. You cannot have small error without small conditional entropy, and you cannot have large conditional entropy without large error. This tight coupling is what makes Fano's inequality so powerful across information theory, statistics, and learning theory.

Visual Beginner

Figure: a diagram showing a message $W$ entering an encoder, producing $X^{n}$ , passing through a noisy channel to produce $Y^{n}$ , and being decoded as $\hat{W}$ . The error indicator $E = 1$ if $\hat{W} \neq = W$ and $E = 0$ otherwise.

Error probability $P_{e}$	$H (P_{e})$ (bits)	$lo g (99) \times P_{e}$	Upper bound on $H (X ∣ Y)$
0.00	0.00	0.00	0.00
0.01	0.08	0.07	0.15
0.10	0.47	0.66	1.13
0.50	1.00	3.31	4.31
0.90	0.47	5.96	6.43

As the error probability grows, so does the upper bound on $H (X ∣ Y)$ : the more errors you make, the less information $Y$ provides about $X$ .

Worked example Beginner

A teacher writes a number from 1 to 10 on a board (uniformly at random). A student sees the number through a noisy display that shows the correct digit with probability 0.8 and a random other digit with probability 0.2.

The student guesses the number. What is the maximum conditional entropy $H (W ∣ Y)$ ?

Using Fano's inequality: $P_{e}$ is the error probability. The optimal guess given $Y = y$ is the most likely value of $W$ , which is $y$ itself (since $P (W = y ∣ Y = y) = 0.8/ (0.8 + 0.2/9) = 0.8/0.822 \approx 0.97$ ).

The error probability is $P_{e} = 1 - 0.973 = 0.027$ .

Fano's bound: $H (W ∣ Y) \leq H (0.027) + 0.027 \times lo g_{2} 9 \approx 0.18 + 0.027 \times 3.17 \approx 0.27$ bits.

So even through a noisy display, the student retains most of the information about the number.

Check your understanding Beginner

Formal definition Intermediate+

Theorem (Fano's inequality). Let $X$ and $Y$ be discrete random variables with $X$ taking values in $X$ with $∣ X ∣ = m$ . Let $\hat{X} (Y)$ be any estimator of $X$ based on $Y$ , and define the error probability $P_{e} = Pr [\hat{X} \neq = X]$ . Then

H (X ∣ Y) \leq H_{b} (P_{e}) + P_{e} lo g_{2} (m - 1),

where $H_{b} (p) = - p lo g_{2} p - (1 - p) lo g_{2} (1 - p)$ is the binary entropy function.

Proof. Define the error indicator $E = 1 [\hat{X} \neq = X]$ . By the chain rule for entropy applied to the pair $(E, X)$ given $Y$ :

H (E, X ∣ Y) = H (E ∣ Y) + H (X ∣ E, Y) .

Since $E$ is binary, $H (E ∣ Y) \leq H (E) = H_{b} (P_{e})$ (conditioning reduces entropy in the other direction: the maximum entropy of a binary variable is $H_{b} (P_{e})$ , achieved when $E$ is independent of $Y$ ).

For the second term, decompose by the value of $E$ :

H (X ∣ E, Y) = Pr [E = 0] \cdot H (X ∣ E = 0, Y) + Pr [E = 1] \cdot H (X ∣ E = 1, Y) .

When $E = 0$ (correct estimate), $X = \hat{X} (Y)$ is determined by $Y$ , so $H (X ∣ E = 0, Y) = 0$ . When $E = 1$ (wrong estimate), $X \neq = \hat{X} (Y)$ , so $X$ lies in $X ∖ {\hat{X} (Y)}$ which has $m - 1$ elements, giving $H (X ∣ E = 1, Y) \leq lo g_{2} (m - 1)$ . Combining:

H (E, X ∣ Y) \leq H_{b} (P_{e}) + (1 - P_{e}) \cdot 0 + P_{e} \cdot lo g_{2} (m - 1) = H_{b} (P_{e}) + P_{e} lo g_{2} (m - 1) .

Since $H (X ∣ Y) \leq H (E, X ∣ Y)$ (adding conditioning variables cannot decrease the joint entropy of the conditioned variables, by the chain rule $H (E, X ∣ Y) = H (X ∣ Y) + H (E ∣ X, Y) \geq H (X ∣ Y)$ ), the result follows. $□$

Counterexamples to common slips

Fano's inequality is an upper bound on $H (X ∣ Y)$ , not a lower bound. It says $H (X ∣ Y)$ cannot be too large when the error probability is small. A small $P_{e}$ forces a small $H (X ∣ Y)$ .
The estimator $\hat{X}$ need not be the MAP estimator. Fano's inequality holds for any estimator. For the MAP estimator (the one minimising $P_{e}$ ), the bound is tightest.
The converse to the channel coding theorem uses a modified form. The standard Fano bound $H (X ∣ Y) \leq 1 + P_{e} lo g m$ (using $H_{b} (P_{e}) \leq 1$ ) is the form used in the converse proof, because it simplifies the algebra.

Key theorem with proof Intermediate+

Theorem (Converse to the channel coding theorem). Let $C = max_{p (x)} I (X; Y)$ be the capacity of a discrete memoryless channel. For any sequence of $(2^{n R}, n)$ codes with average probability of error $P_{e}^{(n)}$ , if $P_{e}^{(n)} \to 0$ as $n \to \infty$ , then $R \leq C$ .

Proof. Consider a $(2^{n R}, n)$ code with message $W$ uniformly distributed over ${1, 2, \dots, 2^{n R}}$ , encoded as $X^{n} (W)$ , transmitted through the channel to produce $Y^{n}$ , and decoded as $\hat{W} (Y^{n})$ .

Step 1. Apply the data processing inequality to the Markov chain $W \to X^{n} \to Y^{n} \to \hat{W}$ :

I (W; Y^{n}) \leq I (X^{n}; Y^{n}) .

Step 2. Expand $I (X^{n}; Y^{n})$ using the memoryless property of the channel ( $p (y^{n} ∣ x^{n}) = \prod_{i} p (y_{i} ∣ x_{i})$ ):

I (X^{n}; Y^{n}) = H (Y^{n}) - H (Y^{n} ∣ X^{n}) = i = 1 \sum n H (Y_{i} ∣ Y^{i - 1}) - i = 1 \sum n H (Y_{i} ∣ X_{i}, Y^{i - 1}) .

Since the channel is memoryless, $H (Y_{i} ∣ X_{i}, Y^{i - 1}) = H (Y_{i} ∣ X_{i})$ , and since conditioning reduces entropy, $H (Y_{i} ∣ Y^{i - 1}) \leq H (Y_{i})$ . But more precisely:

I (X^{n}; Y^{n}) = i = 1 \sum n I (X_{i}; Y_{i}) \leq n C,

where the inequality uses $I (X_{i}; Y_{i}) \leq C$ for each $i$ .

Step 3. By Fano's inequality applied to the estimation of $W$ from $Y^{n}$ :

H (W ∣ Y^{n}) \leq 1 + P_{e}^{(n)} \cdot n R .

Here $∣ W ∣ = 2^{n R}$ , so $lo g ∣ W ∣ = n R$ , and $H_{b} (P_{e}^{(n)}) \leq 1$ .

Step 4. Combine. Since $W$ is uniform on $2^{n R}$ messages, $H (W) = n R$ . Then:

n R = H (W) = I (W; Y^{n}) + H (W ∣ Y^{n}) \leq I (X^{n}; Y^{n}) + 1 + P_{e}^{(n)} n R \leq n C + 1 + P_{e}^{(n)} n R .

Rearranging: $n R (1 - P_{e}^{(n)}) \leq n C + 1$ , so $R \leq \frac{n C + 1}{n ( 1 - P _{e}^{(n)} )} = \frac{C + 1/ n}{1 - P _{e}^{(n)}}$ .

As $n \to \infty$ with $P_{e}^{(n)} \to 0$ : $R \leq C$ . $□$

Bridge. Fano's inequality builds toward the strong converse in 46.03.04, where specific channel models yield exact capacity formulas by combining the achievability proof with the converse derived here. This is exactly the inequality that prevents communication at rates above capacity: the foundational reason is that $H (W ∣ Y^{n}) \leq 1 + P_{e} n R$ forces $P_{e}$ to be bounded away from zero whenever $R > C$ . The central insight is that the error indicator $E$ decomposes conditional entropy into the uncertainty about being wrong and the residual uncertainty about the true value, generalises to list decoding and multi-user settings, and is dual to the achievability proof that shows rates up to $C$ are attainable. Putting these together, Fano's inequality and the channel coding theorem form a complete characterisation of reliable communication, and the bridge is the data processing inequality that constrains information flow through the channel.

Exercises Intermediate+

Exercise (hard, short answer).

Prove that in the converse to the channel coding theorem, the inequality $I (X^{n}; Y^{n}) \leq n C$ holds even when the encoder is allowed to use feedback (i.e., $X_{i}$ may depend on $Y_{1}, \dots, Y_{i - 1}$ ).

Hint

Show that feedback does not change the conditional distribution $p (y_{i} ∣ x_{i})$ and use the chain rule for mutual information.

Answer

With feedback, $X_{i}$ may depend on $Y^{i - 1}$ . By the chain rule:

I (X^{n}; Y^{n}) = i = 1 \sum n I (X^{n}; Y_{i} ∣ Y^{i - 1}) .

For each term: $I (X^{n}; Y_{i} ∣ Y^{i - 1}) = H (Y_{i} ∣ Y^{i - 1}) - H (Y_{i} ∣ X^{n}, Y^{i - 1})$ .

Since the channel is memoryless, $Y_{i}$ depends only on $X_{i}$ , so $H (Y_{i} ∣ X^{n}, Y^{i - 1}) = H (Y_{i} ∣ X_{i})$ . Also, $H (Y_{i} ∣ Y^{i - 1}) \leq H (Y_{i})$ .

More precisely: $I (X^{n}; Y_{i} ∣ Y^{i - 1}) \leq I (X_{i}; Y_{i}) + I (X^{i - 1}; Y_{i} ∣ X_{i}, Y^{i - 1})$ . But $H (Y_{i} ∣ X_{i}, Y^{i - 1}) = H (Y_{i} ∣ X_{i})$ (memoryless channel), so $I (X^{n}; Y_{i} ∣ Y^{i - 1}) = I (X_{i}; Y_{i} ∣ Y^{i - 1}) \leq max_{p (x)} I (X; Y) = C$ .

Summing: $I (X^{n}; Y^{n}) \leq n C$ . This proves that feedback does not increase capacity.

Exercise (hard, short answer).

Show that Fano's inequality is tight in the following sense: for any $P_{e}$ and $m$ , there exist $X$ and $Y$ such that $P_{e} = Pr [\hat{X}_{M A P} \neq = X]$ and $H (X ∣ Y) = H_{b} (P_{e}) + P_{e} lo g_{2} (m - 1)$ .

Answer

Construct $Y$ as follows: with probability $1 - P_{e}$ , $Y$ perfectly reveals $X$ (so $X = Y$ and $H (X ∣ Y) = 0$ ). With probability $P_{e}$ , $Y$ gives no information about $X$ (so $Y$ is constant, independent of $X$ ). In the latter case, $X$ is uniform on $m$ values, contributing $P_{e} \cdot lo g_{2} m$ to $H (X ∣ Y)$ .

The MAP estimator: when $Y$ reveals $X$ , guess correctly ( $E = 0$ ). When $Y$ is uninformative, guess the most likely value of $X$ .

More precisely: let $X$ be uniform on ${1, \dots, m}$ . With probability $1 - P_{e}$ , set $Y = X$ . With probability $P_{e}$ , set $Y = 0$ (a special symbol). Then $H (X ∣ Y) = 0 \cdot (1 - P_{e}) + P_{e} \cdot lo g_{2} m$ . But $P_{e} lo g_{2} m = P_{e} lo g_{2} (m - 1) + P_{e} lo g_{2} (m / (m - 1))$ , which approaches $P_{e} lo g_{2} (m - 1)$ for large $m$ . The MAP error is $P_{e} \cdot (1 - 1/ m) = P_{e} (m - 1) / m$ , not exactly $P_{e}$ . For exact tightness, adjust the construction so that the error event puts $X$ uniformly on $m - 1$ values rather than all $m$ .

Lean formalization Intermediate+

Mathlib does not have a formalization of Fano's inequality or the converse to the channel coding theorem. The conditional entropy $H (X ∣ Y)$ and the chain rule for entropy are absent. A Codex.InformationTheory.FanoConverse module would need to define $H (X ∣ Y)$ , prove the chain rule, establish $H (X ∣ Y) \leq H_{b} (P_{e}) + P_{e} lo g (m - 1)$ using the error indicator decomposition, and derive the converse from the data processing inequality. This is a moderate formalization gap requiring only discrete probability and entropy. This unit ships without a lean_module.

Advanced results Master

The strong converse

The converse proved above shows that $R > C$ implies $P_{e}^{(n)}$ is bounded away from 0. Wolfowitz (1957) proved the strong converse: for $R > C$ , $P_{e}^{(n)} \to 1$ as $n \to \infty$ . Not only can you not achieve vanishing error, but the error probability approaches certainty.

The strong converse uses a refinement of Fano's inequality combined with the Chernoff bound on the probability that the mutual information exceeds its expected value. The key estimate is that for any $ϵ > 0$ :

P_{e}^{(n)} \geq 1 - 2^{- n (R - C - ϵ)} \to 1 for R > C .

Fano's inequality and the Han lower bound

Han (1975) derived a tighter version of Fano's inequality using the information-theoretic framework:

H (X ∣ Y) \geq P_{e} lo g_{2} \frac{1}{P _{e}} + (1 - P_{e}) lo g_{2} \frac{1 - P _{e}}{∣ X ∣ - 1} - P_{e} lo g_{2} \frac{P _{e}}{∣ X ∣ - 1} .

This lower bound complements the upper bound and together they pin down $H (X ∣ Y)$ to within a factor of the range of possible conditional entropies for a given $P_{e}$ .

Applications beyond channel coding

Fano's inequality appears in:

Hypothesis testing: The error probability in distinguishing two distributions is bounded by the Hellinger distance, which relates to KL divergence via Fano-type bounds.
Estimation theory: For parameter estimation, the minimax risk is bounded using a Fano-type inequality applied to the multi-way hypothesis testing problem.
Privacy: Differential privacy bounds use Fano's inequality to show that noisy responses cannot reveal too much about the input.

Synthesis. Fano's inequality is the load-bearing tool that converts an information-theoretic constraint (on conditional entropy) into an operational constraint (on error probability). The central insight is that the decomposition $H (X ∣ Y) \leq H_{b} (P_{e}) + P_{e} lo g (m - 1)$ separates the uncertainty about whether an error occurred from the uncertainty about the true value, and this builds toward every converse result in information theory. The foundational reason Fano's inequality works is that conditioning reduces entropy: knowing $Y$ can only decrease uncertainty about $X$ , and the bound quantifies exactly how much. This is exactly the mechanism that makes the channel coding converse work, generalises to list decoding and multi-user settings, appears again in 46.03.04 as the tool for computing exact channel capacities, and putting these together provides the impossibility side of every fundamental limit in information theory.

Full proof set Master

Proposition (Data processing inequality for mutual information). If $X \to Y \to Z$ forms a Markov chain, then $I (X; Z) \leq I (X; Y)$ .

Proof. Since $Z$ is conditionally independent of $X$ given $Y$ (by the Markov property):

I (X; Z) = I (X; Y, Z) - I (X; Y ∣ Z) = I (X; Y) + I (X; Z ∣ Y) - I (X; Y ∣ Z) .

But $I (X; Z ∣ Y) = 0$ by the Markov property ( $X ⊥ Z ∣ Y$ ), and $I (X; Y ∣ Z) \geq 0$ always. Therefore $I (X; Z) \leq I (X; Y)$ . $□$

Proposition (Feedback does not increase capacity). For a discrete memoryless channel, allowing the encoder to observe previous outputs does not increase the channel capacity.

Proof. With feedback, the encoder at time $i$ observes $Y^{i - 1}$ and produces $X_{i} = X_{i} (W, Y^{i - 1})$ . The mutual information is:

I (W; Y^{n}) = I (X^{n}; Y^{n}) = i = 1 \sum n I (X_{i}; Y_{i} ∣ Y^{i - 1}) .

For each $i$ : $I (X_{i}; Y_{i} ∣ Y^{i - 1}) = H (Y_{i} ∣ Y^{i - 1}) - H (Y_{i} ∣ X_{i}, Y^{i - 1}) = H (Y_{i} ∣ Y^{i - 1}) - H (Y_{i} ∣ X_{i})$ since the channel is memoryless. Therefore $I (X_{i}; Y_{i} ∣ Y^{i - 1}) \leq max_{p (x)} I (X; Y) = C$ . Summing: $I (W; Y^{n}) \leq n C$ . $□$

Connections Master

46.01.01 — Entropy and the chain rule are the foundational ingredients for Fano's inequality; $H (X ∣ Y)$ is defined using conditional entropy from 46.01.01.
46.03.02 — The achievability direction of the channel coding theorem; Fano provides the converse, completing the theorem.
46.03.04 — Specific channel models (BSC, BEC) use Fano's inequality to derive exact capacity formulas.
46.03.01 — Discrete memoryless channels and mutual information; the capacity $C = max_{p} I (X; Y)$ is the quantity that Fano's converse bounds.
46.04.01 — Hypothesis testing uses Fano-type bounds to relate error probabilities to KL divergence.

Historical & philosophical context Master

Robert Fano derived the inequality bearing his name in his 1952 MIT doctoral dissertation and published it in his 1961 monograph "Transmission of Information: A Statistical Theory of Communications" (MIT Press). Fano was building on Shannon's 1948 paper, which had proved the achievability direction of the channel coding theorem but left the converse direction incomplete. Fano's inequality provided the missing tool.

The converse to the channel coding theorem using Fano's inequality was first presented in Fano's 1961 book (Chapters 4-5). The proof technique — introducing the error indicator, applying the chain rule, and bounding each term — became the template for virtually every converse proof in network information theory.

Jacob Wolfowitz proved the strong converse in 1957 ("The coding of messages subject to chance errors," Illinois J. Math. 1, pp. 591-606), showing that not only is $P_{e}^{(n)}$ bounded away from 0 for $R > C$ , but it actually approaches 1. This strengthened Fano's result and established the sharp threshold behaviour of channel coding.

Bibliography Master

@book{fano1961,
  author    = {Fano, R. M.},
  title     = {Transmission of Information: A Statistical Theory of Communications},
  publisher = {MIT Press},
  year      = {1961},
}
@article{wolfowitz1957,
  author  = {Wolfowitz, J.},
  title   = {The Coding of Messages Subject to Chance Errors},
  journal = {Illinois Journal of Mathematics},
  volume  = {1},
  pages   = {591--606},
  year    = {1957},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}
@book{csiszar-korner2011,
  author    = {Csisz{\'a}r, I. and K{\"o}rner, J.},
  title     = {Information Theory: Coding Theorems for Discrete Memoryless Systems},
  edition   = {2nd},
  publisher = {Cambridge University Press},
  year      = {2011},
}

Prerequisites

46.03.02
46.01.01

Tier anchors

beginner: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §2.8 and §7.1-7.4 (the guessing game, why entropy limits decoding, the noisy channel puzzle)
intermediate: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §2.8 (Fano inequality), §7.4-7.6 (converse to the channel coding theorem, feedback does not increase capacity)
master: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §2.8, §7.4-7.7; Csiszar & Korner 2011 Information Theory 2e (Cambridge) §1.2-1.3; Fano 1961 Transmission of Information (MIT Press) Ch. 4-5

References

Cover, T. M. & Thomas, J. A. — Elements of Information Theory (2nd ed.) · Wiley (2006). Section 2.8: Fano's inequality $H (X ∣ Y) \leq H_{b} (P_{e}) + P_{e} lo g_{2} (∣ X ∣ - 1)$ relating conditional entropy to the probability of error in guessing $X$ from $Y$ . Section 7.4: the converse to the noisy channel coding theorem — for any $(2^{n R}, n)$ code with average error probability $P_{e}^{(n)} \to 0$ , the rate $R$ satisfies $R \leq C$ . Section 7.5: Fano's inequality applied to channel coding via $H (W ∣ Y^{n}) \leq 1 + P_{e}^{(n)} n R$ , where $W$ is the message and $Y^{n}$ is the received sequence.
Fano, R. M. — Transmission of Information: A Statistical Theory of Communications · MIT Press (1961). Chapter 4: the inequality relating the probability of error in estimating $X$ from $Y$ to the conditional entropy $H (X ∣ Y)$ . Chapter 5: application to the converse of the coding theorem for discrete memoryless channels. The inequality was derived in lecture notes at MIT in the early 1950s and published in this monograph.
Csiszar, I. & Korner, J. — Information Theory: Coding Theorems for Discrete Memoryless Systems (2nd ed.) · Cambridge University Press (2011). Section 1.2: Fano's inequality and its generalisation (Han's inequality). Section 2.2: the converse coding theorem for DMCs using Fano's inequality and the data processing inequality. The proof shows $n R = H (W) = I (W; Y^{n}) + H (W ∣ Y^{n}) \leq n C + 1 + P_{e} n R$ .

Estimated time

beginner: 15m
intermediate: 45m
master: 90m