= Fano's inequality
{c}
{wiki}
Fano's inequality turns remaining uncertainty into a constraint on decision errors. If an observation leaves many plausible answers, a <decoder> cannot usually recover the answer reliably. Its elegant idea is to separate two uncertainties: whether the guess was wrong, and which alternative was correct when it was wrong.
Let $X,Y$ be <discrete random variables>, with $X$ taking values in a finite <alphabet> $\mathcal X$ of <cardinality> $M\geq2$. Choose any deterministic <decoder> $\widehat X=f(Y)$ whose output lies in $\mathcal X$, and define its average error <probability> $p_e=\mathbb P\{\widehat X\ne X\}$. With base-two <logarithms>, <Fano's inequality> states
$$
H(X\mid Y)\leq h_2(p_e)+p_e\log_2(M-1),\qquad 0\leq p_e\leq1.
$$
Here $H(X\mid Y)$ is <conditional entropy> and $h_2$ is <binary entropy>, with $0\log_2 0=0$ at the endpoints. Both sides are measured in <bits>; using <natural logarithms> throughout gives the same inequality in <nats>. No uniform source, independence of $X,Y$, or optimality of the <decoder> is assumed. Requiring its output to belong to the same <alphabet> is what leaves at most $M-1$ alternatives after an error.<6.441 Information Theory (Spring 2016 lecture notes) by Yury Polyanskiy and others>[Polyanskiy and Wu, MIT 6.441 course notes, Section 5.3, Theorem 5.3]{ref}
For an exact toy example, give $X$ the <discrete uniform distribution> on $\{A,B,C,D\}$. A <channel> reports $Y=X$ with <probability> $1-q$ and reports each of the other three symbols with <probability> $q/3$, where $0\leq q\leq1$. Use the <decoder> $f(y)=y$. The output is uniform, and the <conditional probabilities> after any report $y$ are
$$
\mathbb P(X=x\mid Y=y)=
\begin{cases}
1-q,&x=y,\\
q/3,&x\ne y.
\end{cases}
$$
Thus $p_e=q$ and direct calculation of the <conditional entropy> gives
$$
H(X\mid Y)=-(1-q)\log_2(1-q)-3\frac q3\log_2\frac q3
=h_2(q)+q\log_2 3.
$$
This is equality in <Fano's inequality> for every $q\in[0,1]$. At $q=0.3$, each report leaves <probabilities> $(0.7,0.1,0.1,0.1)$, up to their order, and $H(X\mid Y)\approx1.3568$ <bits>. The two contributions are $h_2(0.3)\approx0.8813$ <bits> for the error flag and $0.3\log_2 3\approx0.4755$ <bits> for identifying the correct alternative after an error. These are theoretical <probabilities>, not measured data.
\Image[/fano-four-symbol-posterior.png]
{title=A symmetric four-symbol toy channel makes every step of Fano's bound an equality}
The identity <decoder> in this example minimizes error only for $0\leq q\leq3/4$: its guessed symbol has the largest <posterior probability> exactly when $1-q\geq q/3$. At $q=3/4$, $X,Y$ are <independent random variables> and all four guesses tie. For $q>3/4$, guessing any one of the three other symbols has error <probability> $1-q/3<q$. Equality in <Fano's inequality> therefore does not certify an optimal <decoder>.
For usefulness, combine $h_2(p_e)\leq1$ with $\log_2(M-1)\leq\log_2 M$ to obtain the simpler consequence
$$
p_e\geq\max\!\left\{0,\frac{H(X\mid Y)-1}{\log_2 M}\right\}.
$$
For a uniform $X$, $H(X\mid Y)=\log_2 M-I(X;Y)$, so this becomes $p_e\geq\max\{0,1-(I(X;Y)+1)/\log_2 M\}$. This connects <mutual information> to unavoidable decision error in <channel coding> or <classification in statistical learning>; it can rule out reliable recovery regardless of the chosen <decoder>.https://web.stanford.edu/class/ee376a/files/lecture_notes.pdf[Weissman, Ochoa and Tatwawadi, EE376A course notes, Sections 5.7–5.8]{ref}
The sharper right-hand side $F_M(p)=h_2(p)+p\log_2(M-1)$ increases from zero to $\log_2 M$ on $0\leq p\leq1-1/M$, then decreases: in the interior, $F_M'(p)=\log_2((M-1)(1-p)/p)$. When interpreting the inequality by inverting a curve, use its increasing branch to obtain a lower error threshold. A <decoder> that chooses a largest <posterior probability>, as in <maximum a posteriori decoding>, always has $p_e\leq1-1/M$, since the largest of $M$ conditional <probabilities> is at least $1/M$. Arbitrary <decoders> can have larger error. In particular, low <conditional entropy> does not force every <decoder> to work well: with a fair binary $X$ and $Y=X$, the rule $f(Y)=1-Y$ has $p_e=1$ even though $H(X\mid Y)=0$. <Fano's inequality> supplies a constraint, not an exact error prediction for each rule.
Back to article page
