Past exam of the information theory course of the University of Oxford / 2023 / 1 / b

Let $N=|\mathcal{X}|\ge 2$ and let $E=1_{\{X\ne Y\}}$ be the error indicator random variable. Because $E$ is determined by $(X,Y)$, the chain rule for conditional entropy in its two orders givesBy conditioning reduces entropy, $H(E\mid Y)\le H(E)$. On $E=0$, knowing $Y$ determines $X$, so the corresponding conditional entropy is zero. On $E=1$, at most $N-1$ symbols remain possible for $X$. The maximum Shannon entropy of a probability distribution on at most $N-1$ symbols is $\log (N-1)$. ConsequentlyFor an arbitrary function $g:\mathcal{X}\to \mathcal{X}$, repeat the argument with $E_g=1_{\{X\ne g(Y)\}}$. This is still determined by $(X,Y)$; when it is zero, $X=g(Y)$, and when it is one, $X$ has at most $N-1$ possibilities for each $Y$. Thus Fano's inequality givesEvents of zero probability contribute zero to the conditional average, covering the error probabilities zero and one. If $N=1$, the left side and error probabilities are zero; the trivial conclusion is handled separately instead of writing $0\log 0$ as an ordinary finite product.