Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 60 / 2 / ii

The error indicator is a Bernoulli random variable with probabilities $P(Z=1)=p_e$ and $P(Z=0)=1-p_e$. Its Shannon entropy is therefore the binary entropyUse $0{\log }_{2}0=0$, so this expression also covers error probabilities zero and one.

Apply the definitions of conditional entropy and insert $H(X,Y)$:Inserting $H(Z,Y)$ instead gives the alternative chain rule for conditional entropyBoth are expansions of the same joint conditional uncertainty, with the variables exposed in opposite orders.

Because $Z$ is determined by $X,Y$, its conditional entropy satisfies $H(Z\mid X,Y)=0$. Equate the two forms of the chain rule for conditional entropy to obtainConditioning cannot increase classical Shannon entropy: $H(Z)-H(Z\mid Y)=I(Z:Y)\ge 0$ by nonnegativity of mutual information. Thus $H(Z\mid Y)\le H(Z)=h(p_e)$. When $Z=0$, the value of $X$ is exactly $f(Y)$ and $H(X\mid Y,Z=0)=0$. When $Z=1$ and $Y=y$, the value $f(y)$ is excluded, leaving at most $|J_X|-1$ possibilities. By maximum entropy on a finite alphabet,Averaging the two conditional cases now yieldsand consequentlyThis is Fano's inequality via an error indicator. Events of zero probability contribute zero to the average and need no conditional distribution. For $|J_X|=1$, the inference is automatically correct and the entropy is zero; the displayed logarithmic form is intended for $|J_X|\ge 2$. Optimality of the guess is not needed for the inequality: it holds for every deterministic $f$.