= Solution
Apply <Gibbs inequality> to the <joint distribution> and the product of its marginals. Restrict to the Cartesian product of their positive supports, so the reference probabilities are strictly positive as the supplied inequality requires. Expanding gives
$$
0\leq\sum_{x,y}p(x,y)\log_2\frac{p(x,y)}{p_X(x)p_Y(y)}
=H(X)-H(X\mid Y).
$$
This proves the second inequality. For the first, apply the same argument to the conditional <joint distribution> of $(X,Z)$ for each $y$ with $p_Y(y)>0$, and average with those probabilities:
$$
0\leq\sum_y p_Y(y)I(X;Z\mid Y=y)
=H(X\mid Y)-H(X\mid Y,Z).
$$
Here the conditional support restriction again removes zero marginal probabilities. Thus
$$
\boxed{H(X\mid Y,Z)\leq H(X\mid Y)\leq H(X)}.
$$
The nonnegative differences are <conditional mutual information> and <mutual information>, respectively.
Back to article page
