Questions: Fano's Inequality

Question 1

An estimator guesses a random variable X (which takes 8 values) from observation Y with error probability P_e = 0.01. What does Fano's inequality tell us about H(X|Y)?

• A. H(X|Y) = 0, because the estimator is nearly perfect
• B. H(X|Y) <= H(0.01) + 0.01 * log2(7) ≈ 0.081 + 0.028 = 0.109 bits — the conditional entropy must be small because the estimation is accurate
• C. H(X|Y) <= 3 bits (the full entropy of a uniform 8-valued variable)
• D. Fano's inequality cannot be applied when the error probability is below 0.5

Answer: (B)

Fano's inequality gives H(X|Y) <= H(P_e) + P_e * log2(|X|-1) = H(0.01) + 0.01 * log2(7) ≈ 0.081 + 0.028 = 0.109 bits. The small error probability forces H(X|Y) to be small — Y carries almost all the information about X. This is the inequality's power: low estimation error implies high information content, which constrains what communication rates are possible.

Question 2

Fano's inequality provides a LOWER bound on the conditional entropy H(X|Y).

• T. True
• F. False

Answer: False

Fano's inequality provides an UPPER bound on H(X|Y): it says H(X|Y) is at most H(P_e) + P_e * log(|X|-1). However, its typical use is to derive a LOWER bound on error probability: rearranging, P_e >= (H(X|Y) - 1) / log(|X|-1). If H(X|Y) is large (Y carries little information about X), then P_e must be large. This makes it a tool for proving impossibility: high conditional entropy implies high error probability.

Question 3

Explain how Fano's inequality is used to prove the converse of the channel coding theorem — that reliable communication above channel capacity is impossible.

Model answer: Consider transmitting one of 2^(nR) messages over n uses of a channel with capacity C. The message M is estimated as M-hat from the channel output Y^n. Fano's inequality gives H(M|Y^n) <= 1 + P_e * nR. Meanwhile, the data processing inequality and the capacity definition give I(M; Y^n) <= nC. Since I(M; Y^n) = H(M) - H(M|Y^n) = nR - H(M|Y^n), combining yields nR - 1 - P_e * nR <= nC. If R > C, then for large n, P_e must be bounded away from zero — the error probability cannot vanish. Therefore, reliable communication at rate R > C is impossible.

The converse proof chains together Fano's inequality (connecting error probability to conditional entropy), the definition of mutual information (connecting conditional entropy to information rate), and the channel capacity bound (capping mutual information per channel use). Each link is individually simple; their composition yields the profound result that capacity is a hard ceiling.