Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)

share|improve this question

2 Answers 2

up vote 6 down vote accepted

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

share|improve this answer
    
Or we can write $H(X|Z)\geq H(X|ZY)$ and hence $H(Z|Y)+H(X|Z)\geq H(Z|Y)+H(X|ZY)=H(XZ|Y)\geq H(X|Y)$. –  Arash Jan 13 at 1:32

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.