Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 1 / 3G / Solution

For finite-valued discrete random variables, the conditional entropy isThe chain rule for information entropy in two orders givesThereforeusing nonnegativity of conditional entropy and the fact that conditioning reduces entropy. This proves the required inequality.

For Fano's inequality, let $X$ take values in an alphabet of size $m$, let $\hat{X}=g(Y)$ be any estimator, and putBecause $E$ is determined by $(X,Y)$,Now $H(E\mid Y)\le H(E)=h_2(p_e)$. If $E=0$, $X$ is determined by $Y$; if $E=1$, at most $m-1$ values remain possible. HenceCombining the bounds yields