Back to the on-screen lesson · Print

Fano's inequality

How much uncertainty a guess can leave behind, and why leftover uncertainty forces every estimator to fail often.

Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.

1. What you will learn

By the end of this lesson you will be able to split Fano's bound into its two parts and evaluate each, assemble its proof from the error indicator and the chain rule, turn a conditional entropy into a floor under the error probability of every estimator, say why that floor is a limit rather than a promise, and read the same inequality as a security guarantee about guessing a secret.

2. What you already have

Conditional entropy, the chain rule, the binary entropy function, and the data processing inequality. This lesson connects entropy to something you can observe: how often a guess is wrong.

3. Estimator, error probability, error indicator

An estimator $\hat{X} = g(Y)$ is any rule for guessing $X$ from $Y$, and its error probability is $P_e = P(\hat{X} \ne X)$. The proof introduces the error indicator $E$, the bit that records whether the guess was wrong. Fano's inequality budgets the leftover uncertainty in terms of these.

4. Fano's inequality

Suppose you estimate $X$ from $Y$ by some rule $\hat{X} = g(Y)$ and let $P_e = P(\hat{X} \ne X)$. Fano's inequality bounds the uncertainty that remains: $$H(X \mid Y) \le h(P_e) + P_e \log_2(|\mathcal{X}| - 1) \le 1 + P_e \log_2 |\mathcal{X}|.$$ The proof introduces the error indicator $E$ and expands $H(E, X \mid \hat{X})$ two ways: knowing whether the guess was wrong costs at most $h(P_e)$, and if it was wrong, naming the true value among the remaining $|\mathcal{X}| - 1$ costs at most $\log_2(|\mathcal{X}| - 1)$. Read in reverse it is the important direction: if $H(X \mid Y)$ is large, then every estimator has $P_e \ge \dfrac{H(X \mid Y) - 1}{\log_2 |\mathcal{X}|}$. Fano is the tool that turns entropy statements into statements about error probabilities, and it is the heart of the converse to the channel coding theorem: at rates above capacity too much uncertainty about the message survives, so decoding must fail.

5. The proof in full

Let $\hat{X} = g(Y)$ be any estimator and $E$ the indicator of an error, $E = 1$ when $\hat{X} \ne X$, so $P(E = 1) = P_e$. Expand $H(E, X \mid \hat{X})$ in two orders. First: $H(E, X \mid \hat{X}) = H(X \mid \hat{X}) + H(E \mid X, \hat{X}) = H(X \mid \hat{X})$, because $E$ is determined by $X$ and $\hat{X}$. Second: $H(E, X \mid \hat{X}) = H(E \mid \hat{X}) + H(X \mid E, \hat{X})$. Now bound the two pieces. $H(E \mid \hat{X}) \le H(E) = h(P_e)$. And $H(X \mid E, \hat{X}) = P(E = 0) \cdot 0 + P_e \cdot H(X \mid E = 1, \hat{X}) \le P_e \log_2 (|\mathcal{X}| - 1)$: if the guess is right there is nothing left to say, and if it is wrong the truth is one of the other $|\mathcal{X}| - 1$ values. Finally $H(X \mid Y) \le H(X \mid \hat{X})$ by data processing, since $X \to Y \to \hat{X}$. Altogether: $$H(X \mid Y) \le h(P_e) + P_e \log_2 (|\mathcal{X}| - 1).$$ Weakening $h(P_e) \le 1$ and $|\mathcal{X}| - 1 \le |\mathcal{X}|$ gives the memorable form $H(X \mid Y) \le 1 + P_e \log_2 |\mathcal{X}|$.

6. Reading the bound both ways

For a variable with $17$ values, $\log_2 (|\mathcal{X}| - 1) = \log_2 16 = 4$, and the bound as a function of $P_e$ looks like this:

Forwards, given $P_e$: the remaining uncertainty $H(X \mid Y)$ cannot exceed the bound; a good estimator certifies that $Y$ says a lot about $X$. Backwards, given $H(X \mid Y)$: read across the horizontal line to where the curve reaches it; every estimator has at least that error probability. With the weak bound this is a formula, $$P_e \ge \frac{H(X \mid Y) - 1}{\log_2 (|\mathcal{X}| - 1)},$$ and the backwards reading is the one that proves converses: if a channel leaves $H(X \mid Y)$ large, reliable decoding is impossible no matter how clever the decoder.

7. Solving the practice problems

1. Upper bound on $H(X \mid Y)$ from $P_e$, with $2^k + 1$ values: $\log_2 (|\mathcal{X}| - 1) = k$, so the bound is $h(P_e) + k P_e$; take $h(P_e)$ from the table.
2. Smallest $P_e$ from $H(X \mid Y) = c$ with the weak bound: $P_e \ge (c - 1) / k$.
3. What Fano lets you conclude: a lower bound on the error of every estimator from the conditional entropy, or an upper bound on the conditional entropy from a good estimator. It never says an estimator achieves the bound.

Common mistakes

• Using $\log_2 |\mathcal{X}|$ where the problem states the sharp form with $|\mathcal{X}| - 1$; with $2^k + 1$ values the difference is exactly what makes the logarithm come out as the integer $k$.
• Forgetting the $h(P_e)$ term in the sharp bound, or the $1$ in the weak one.
• Reading the lower bound on $P_e$ as an achievable error rate: it is a floor, not a promise.

8. Where this usually goes wrong

The first error is using $\log_2 |\mathcal{X}|$ where the sharp form asks for $\log_2(|\mathcal{X}| - 1)$; with $2^k + 1$ values the difference is exactly what makes the logarithm come out as the whole number $k$. The second is dropping the $h(P_e)$ term from the sharp bound, or the $1$ from the weakened one, which changes the answer by up to a whole bit. The third, and the one that matters most, is reading the lower bound on $P_e$ as an achievable error rate: it is a floor, not a promise, and an estimator may be far worse than it. Fano never says an estimator attains anything.

9. Bounding the error

1. $X$ takes $17$ values and $H(X \mid Y) = 3$ bits. Weakened Fano: $3 \le 1 + P_e \log_2 16 = 1 + 4 P_e$.

   Plug in $|\mathcal{X}| - 1 = 16$.

2. $P_e \ge \tfrac{1}{2}$: any estimator is wrong at least half the time.

   Uncertainty forces errors.

10. Sketch of the proof

1. Let $E = 1$ if $\hat{X} \ne X$. Chain rule: $H(E, X \mid \hat{X}) = H(X \mid \hat{X}) + H(E \mid X, \hat{X}) = H(X \mid \hat{X})$, since $E$ is determined by $X$ and $\hat{X}$.

   First expansion.

2. Also $= H(E \mid \hat{X}) + H(X \mid E, \hat{X}) \le h(P_e) + P_e \log_2(|\mathcal{X}| - 1)$; and $H(X \mid Y) \le H(X \mid \hat{X})$ by data processing.

   When $E = 0$ nothing is left; when $E = 1$ at most $\log_2(|\mathcal{X}| - 1)$.

11. Upper bound with $9$ values and $P_e = 0.1$

1. $|\mathcal{X}| - 1 = 8$, so $\log_2 8 = 3$.

2. $h(0.1) = 0.469$ and $P_e \log_2 8 = 0.3$.

3. $H(X \mid Y) \le 0.469 + 0.3 = 0.769$ bits: an estimator right $90\%$ of the time certifies that less than $0.77$ bits of $X$ remain hidden.

12. Lower bound on the error with $33$ values and $H(X \mid Y) = 3$

1. Weak bound: $3 \le 1 + P_e \log_2 32 = 1 + 5 P_e$.

2. $P_e \ge \tfrac{3 - 1}{5} = 0.4$.

3. Every estimator of $X$ from $Y$ is wrong at least $40\%$ of the time; the sharp bound would push this floor a little higher.

13. Your turn: binary $X$ with $H(X \mid Y) = 0.5$; what does Fano say about $P_e$?

1. $|\mathcal{X}| - 1 = 1$, so $\log_2 1 = 0$ and Fano reads $0.5 \le h(P_e)$.

2. Your turn: work this step out. Its working is at the end of the packet.

   $h(P_e) \ge 0.5$ forces $P_e \ge 0.11$: at least $11\%$ errors.

14. Guided practice

$X$ takes $9$ values and a guess $\hat{X}(Y)$ is wrong with probability $P_e = 0.3$. Fill in the two parts of Fano's bound on $H(X \mid Y)$ and their total, in bits.

15. Guided practice

Build the proof of Fano's inequality, $H(X \mid \hat{X}) \le h(P_e) + P_e \log_2(|\mathcal{X}| - 1)$.

This task has no paper form; do it on a device.

16. Practice

$X$ takes $257$ values, so $\log_2(|\mathcal{X}| - 1) = 8$. Using the weakened bound $H(X \mid Y) \le 1 + P_e \cdot 8$, match each value of $H(X \mid Y)$ to the smallest error probability it forces on any estimator.

17. Practice

$X$ takes $129$ values and $H(X \mid Y) = 4$ bits. Using the weakened Fano bound $H(X \mid Y) \le 1 + P_e \log_2(|\mathcal{X}| - 1)$, what is the smallest possible error probability of any estimator of $X$ from $Y$?

Answer:

18. Somewhere new

A secret key $X$ is one of $65$ equally likely strings. An attacker observes a side channel $Y$, after which $H(X \mid Y) = 5$ bits remain. Using the weakened Fano bound, give the set of error probabilities the attacker's single best guess could have, as an interval.

This task has no paper form; do it on a device.

19. Lesson test

Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.

20. Test question

What does Fano's inequality let you conclude?

• Large $H(X \mid Y)$ forces every estimator of $X$ from $Y$ to have a large error probability
• The error probability of the best estimator equals $H(X \mid Y)$
• Any estimator with $P_e < 1/2$ makes $H(X \mid Y) = 0$

21. What you can do now

You can turn leftover uncertainty into an error floor and say exactly what the floor does and does not claim. Say in your own words what the two terms of Fano's bound are paying for. This closes the unit on divergence and information; next comes source coding, and the codes that reach the entropy.

Working for the steps left to you

13. Your turn: binary $X$ with $H(X \mid Y) = 0.5$; what does Fano say about $P_e$?, step 2