Inequality in information theory

Question

I am reading the paper "chain independence and common information" (http://ttic.uchicago.edu/~yury/papers/independ.pdf). In this paper, an inequality is used several times (without proof) which looks interesting to me. I would appreciate if anybody can help me prove it. The inequality is as follows: For random variables $X$, $Y$, $Z$ we have $$H(Z)\leq H(Z|X) + H(Z|Y) + I(X;Y)$$ where $H(\cdot)$ is the entropy and $I(\cdot;\cdot)$ is mutual information.

As far as I see in the paper, there is no restriction on the structure of random variables $X,Y$ and $Z$, so they are arbitrary. (Look at the first page or second page of the paper in the proof of Theorem I)

Answer 1

The answer is as follows. We need to show that

$$I(Z; X)-I(X; Y)\leq H(Z|Y).$$ The left hand side of this is simplified as $H(X|Y)-H(X|Z)$, so we need to show that $H(X|Y)-H(X|Z)\leq H(Z|Y)$. Since conditioning reduces the entropy we have $$H(X|Y)-H(X|Z)\leq H(X|Y)-H(X|Y,Z)=I(X;Z|Y)\leq H(Z|Y).$$

Answer 2

I'd prefer to keep the symmetry of $X$ and $Y$ in the argument. Then $$ H(Z|X) + H(Z|Y) + I(X,Y) \\ = H(X\vee Z) - H(X) + H(Y\vee Z) - H(Y) + H(X) +H(Y) -H(X\vee Y) \\ = H(X\vee Z) + H(Y\vee Z) - H(X\vee Y) \\ = 2 H(Z) + H(X|Z) + H(Y|Z) - H(X\vee Y) \\ \ge 2H(Z) + H(X\vee Y|Z) - H(X\vee Y) \\ = H(Z) + H(X\vee Y\vee Z) - H(X\vee Y) \\ \ge H(Z) $$ Several lines here are totally obvious, but I preferred to keep all the details. In what concerns the notation, I have actually replaced the random variables from the original formulation with the associated partitions of the base probability space (so that the partition $X\vee Y$ corresponds to the joint distribution of $X$ and $Y$, etc.). Actually the language of partitions is much more appropriate for dealing with problems of this kind. Of course, this argument (as well as the original question) only makes sense if all the partitions ($\equiv$ random variables) involved are discrete and have finite entropy.