Fano's Inequality

H(X | Y) ≤ H(P_e) + P_e (| X| - 1) — the universal lower bound on estimation error.

The idea

Theorem (Fano's inequality).

Let $X$ take values in a finite alphabet $\mathcal{X}$, let $Y$ be an observation, and let $\hat{X} = \hat{X}(Y)$ be any estimator of $X$ computed from $Y$, with error probability $P_e = \mathbb{P}(\hat{X} \neq X)$. Then $H(X \mid Y) \leq H(P_e) + P_e \log(|\mathcal{X}| - 1),$ where $H(P_e) = -P_e \log P_e - (1 - P_e)\log(1 - P_e)$ is the binary entropy and both sides use the same base of logarithm.

Base $2$ gives bits. The force of the inequality lies in its contrapositive. If much uncertainty about $X$ survives the observation — if $H(X \mid Y)$ is large — then the right-hand side must be large as well, and the only quantity there free to grow is $P_e$. Large residual entropy therefore forces a floor under the error probability.

Two features of the bound matter in applications. It holds for every estimator, which is what makes it the standard instrument for proving a task impossible. And the alphabet enters only through $\log(|\mathcal{X}| - 1)$: once the guess is known to be wrong, $|\mathcal{X}| - 1$ candidates remain, so identifying $X$ among them costs at most $\log(|\mathcal{X}| - 1)$ bits.

Ways to work on it

• Walkthrough. Read off Fano, apply it to the binary symmetric channel, and carry out the proof's key step.
• Practice. Turn a ceiling on the mutual information into a numerical lower bound on decoding error.
• Hardest. Apply Fano's converse to get a hard lower bound on decoding error.

Not sure where to start? Take the ten-question placement test.