= Solution
For finite-valued <random variable>[discrete random variables], the <conditional entropy> is
$$
H(X\mid Y)
=\sum_y\mathbb P(Y=y)H(X\mid Y=y)
=-\sum_{x,y}p(x,y)\log_2p(x\mid y).
$$
The <chain rule for information entropy> in two orders gives
$$
H(X,Z\mid Y)
=H(X\mid Y)+H(Z\mid X,Y)
=H(Z\mid Y)+H(X\mid Y,Z).
$$
Therefore
$$
H(X\mid Y)
=H(X\mid Y,Z)+H(Z\mid Y)-H(Z\mid X,Y)
\leq H(X\mid Y,Z)+H(Z),
$$
using 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 $\widehat X=g(Y)$ be any estimator, and put
$$
E=\boldsymbol1_{\{\widehat X\ne X\}},
\qquad p_e=\mathbb P(E=1).
$$
Because $E$ is determined by $(X,Y)$,
$$
H(X\mid Y)=H(E,X\mid Y)
=H(E\mid Y)+H(X\mid E,Y).
$$
Now $H(E\mid Y)\leq H(E)=h_2(p_e)$. If $E=0$, $X$ is determined by $Y$; if $E=1$, at most $m-1$ values remain possible. Hence
$$
H(X\mid E,Y)
\leq p_e\log_2(m-1).
$$
Combining the bounds yields
$$
\boxed{H(X\mid Y)
\leq h_2(p_e)+p_e\log_2(m-1)}.
$$
Back to article page
