Fano's Inequality

Core Idea

Fano's inequality relates the probability of error in estimating a random variable X from an observation Y to the conditional entropy H(X|Y). Specifically, if X-hat = g(Y) is any estimator of X from Y with error probability P_e = Pr(X-hat != X), then H(X|Y) <= H(P_e) + P_e * log(|X| - 1), where H(P_e) is the binary entropy. Equivalently, low error probability implies low conditional entropy: if you can estimate X well from Y, then Y must carry a lot of information about X. Fano's inequality is the primary tool for proving converse (impossibility) results in information theory, including the converse of the channel coding theorem.

Explainer

Fano's inequality connects two seemingly different quantities: the probability of making an error when estimating X from Y, and the conditional entropy H(X|Y). The intuition is straightforward: if Y contains a lot of information about X (H(X|Y) is small), then a good estimator should rarely be wrong (P_e is small). Fano's inequality makes this intuition precise and quantitative.

The inequality states: H(X|Y) <= H(P_e) + P_e * log(|X| - 1). The first term, H(P_e) = -P_e log P_e - (1-P_e) log(1-P_e), is the entropy of the error event itself — it is at most 1 bit and decreases as P_e approaches 0 or 1. The second term, P_e * log(|X|-1), accounts for the uncertainty about which of the |X|-1 wrong values X takes when an error occurs. Together, they bound how much residual uncertainty H(X|Y) can exist given error probability P_e.

The inequality is most powerful when inverted: rearranging, P_e >= (H(X|Y) - 1) / log(|X|-1). If Y carries little information about X — meaning H(X|Y) is close to its maximum H(X) — then the error probability must be large. This is a converse tool: it proves that accurate estimation is impossible when the mutual information I(X;Y) = H(X) - H(X|Y) is small relative to H(X).

The central application is proving that rates above channel capacity are unachievable. In this context, X = M (the message) and Y = Y^n (the channel output). Fano's inequality converts the assumption of low error probability into a constraint on H(M|Y^n), which in turn constrains the rate R through the mutual information chain. The resulting proof is clean and powerful: any attempt to communicate faster than capacity is mathematically guaranteed to produce non-vanishing errors. Fano's inequality appears throughout information theory wherever converse proofs are needed — in source coding, multi-user information theory, hypothesis testing, and statistical estimation.