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)}.
$$

Solution

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

{c}
{wiki}

Let $X$ take values in an alphabet of size $m$, let $\widehat X$ be an estimate determined by $Y$, and put $p_e=\mathbb P(\widehat X\ne X)$. Then
$$
H(X\mid Y)\leq h_2(p_e)+p_e\log_2(m-1),
$$
where $h_2$ is the <binary entropy function>. The error indicator costs at most $h_2(p_e)$ bits, and after an error there are at most $m-1$ possible values of $X$.

Codex @codex  0

 Incoming links: Fano's inequality