= Fano's inequality via an error indicator
{c}
{title2=$H(X\mid Y)\leq h(p_e)+p_e\log_2(|J_X|-1)$}
Under the hypotheses of <Fano's inequality>, let $J_X=\mathcal X$, $M=|J_X|$, and let $Z=\mathbf1_{\{X\ne f(Y)\}}$ be the <indicator random variable> of an error. Its <probability> of being one is $p_e$. The $h$ in the displayed bound denotes <binary entropy> $h_2$ in <bits>. Since $Z$ is a deterministic <function> of $(X,Y)$, $H(Z\mid X,Y)=0$. Applying the <chain rule for conditional entropy> in both orders gives the exact decomposition
$$
\begin{aligned}
H(X\mid Y)
&=H(X,Z\mid Y)\\
&=H(Z\mid Y)+H(X\mid Z,Y).
\end{aligned}
$$
The first term is bounded by $H(Z)=h_2(p_e)$, because <conditioning reduces entropy>. For the second term, fix a report $Y=y$: if $Z=0$, then $X=f(y)$ is known; if $Z=1$, then $X$ lies among at most $M-1$ other symbols. <Maximum entropy on a finite alphabet> bounds the latter uncertainty by $\log_2(M-1)$. Averaging over the reports and the error flag gives
$$
H(X\mid Z,Y)\leq(1-p_e)\cdot0+p_e\log_2(M-1).
$$
This proves <Fano's inequality>. Events of zero <probability> contribute zero to this average, so the proof also covers $p_e=0,1$ without assigning a conditional distribution to an impossible event.https://web.stanford.edu/class/ee376a/files/lecture_notes.pdf[Weissman, Ochoa and Tatwawadi, EE376A course notes, Section 5.7, proof of Theorem 46]{ref}
\Image[/fano-error-entropy-budget.png]
{title=The four-symbol entropy budget peaks at chance-level error and separates the error flag from the three alternatives}
The decomposition also explains equality. The first bound is exact when the <indicator random variable> $Z$ and $Y$ are <independent random variables>: knowing the report does not change the error <probability>. The second is exact when, for every report with positive error <probability>, the wrong-symbol <conditional distribution> is uniform on all $M-1$ alternatives. Both conditions hold in the four-symbol toy <channel> of <Fano's inequality>. At $q=0$, the second condition is vacuous; at $q=1$, the flag is constant but three alternatives remain, giving $H(X\mid Y)=\log_2 3$. For $M=2$, there is just one alternative after an error, so the second term vanishes: all remaining uncertainty is whether the single alternative must replace the guess.
Back to article page
