Fano’s Inequality

Suppose that Alice wants to transmit a random variable $X$ to Bob via a noisy channel. The noisy channel is modelled by a stochastic mapping $f$, and Bob receives a randomized version of $X$, denoted as $Y = f(X)$. Bob post-processes $Y$ by another stochastic mapping $g$ to produce an estimate $\hat X$ of $X$. The mapping $g$ depends only on $Y$ and therefore $\hat X$ and $X$ are conditionally independent given $Y$. The random variables $X$, $Y$ and $\hat X$ forms a Markov chain, denoted as

Denote $p_e = \Pr[ \hat X \neq X]$ the probability of estimation error. If the channel is noiseless, then $H(X \mid Y ) = 0$, and the identity mapping $g(Y) \doteq Y$ has error probability $p_e = 0$. As the noisy of the channel increases, $H(X \mid Y)$ increases, so as $p_e$. $H(X \mid Y)$ can be viewed as the information lost incurred by the channel. The information lost is small, only if when $p_e$ is small, which is established by the following theorem.

Theorem (Fano's Inequality). Suppose that the random variables $X \rightarrow Y \rightarrow \hat X$ forms a Markov chain. Let $p_e \doteq \Pr[ X \neq \hat X]$. The information lost of $H(X \mid Y)$ is bounded by:

$$H(X \mid Y) \le H ( X \mid \hat X) \le H_2(p_e) + p_e \log ( | \Omega | - 1),$$

where $H_2(p) \doteq p \cdot \big( \log \frac{1}{p} \big) + (1 - p) \cdot \log \frac{1}{1 - p}$.

Remark. Note that

which complies with our discussion before.

Proof. Let $E$ be an indicator random variable for the event $X \neq \hat X$.

Via chain rule for entropy, we expand $H(E, X \mid \hat X)$ in two different ways

We see that

• $H(E \mid X, \hat X) = 0$, since $E$ is a function of $X$ and $\hat X$, the conditional entropy.

• $H( E \mid \hat X ) \le H(E) = H_2 (p_e)$, since conditioning reduces entropy and $E$ is a binary random variable.

• $H(X \mid E, \hat X) \le p_e \log ( | \Omega | - 1)$, which is obtained as follows:

  $$\begin{aligned} H(X \mid E, \hat X) &= p_e H( X \mid \hat X, E = 1) + (1 - p_e) H(X \mid \hat X, E = 0) \\ &\le p_e \log ( | \Omega | - 1). \end{aligned}$$

  The last inequality holds, since given $\hat X$,

  1. when $E = 0$, there is no randomness about $X$; and

  2. when $E = 1$, $X$ has $|\Omega - 1|$ possible outcomes and its randomness is less than the one of uniform distribution over the possible outcomes.

Combining these results, we get

It is left to prove that

Via the data-processing inequality for the Markov chain $X \rightarrow Y \rightarrow \hat X$:

which implies

$\square$

Reference

[1] T. M. Cover and J. A. Thomas, “ELEMENTS OF INFORMATION THEORY,” p. 774.