Fano's inequality via an error indicator ($H(X\mid Y)\le 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=1_{\{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 decompositionThe 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 givesThis 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.^[ref]

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.