= Solution
Let $N=|\mathcal X|\geq2$ and let $E=\mathbf1_{\{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 gives
$$
H(X\mid Y)=H(X,E\mid Y)=H(E\mid Y)+H(X\mid E,Y).
$$
By <conditioning reduces entropy>, $H(E\mid Y)\leq 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)$. Consequently
$$
\boxed{H(X\mid Y)\leq H(\mathbf1_{\{X\ne Y\}})+\Pr(X\ne Y)\log(N-1).}
$$
For an arbitrary <function> $g:\mathcal X\to\mathcal X$, repeat the argument with $E_g=\mathbf1_{\{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> gives
$$
\boxed{H(X\mid Y)\leq H(\mathbf1_{\{X\ne g(Y)\}})+\Pr(X\ne g(Y))\log(N-1).}
$$
Events 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\log0$ as an ordinary finite product.
Back to article page
