0
$\begingroup$

I am trying to prove three properties of entropy.

$1)$ $H(X|Y,Z)\le H(X|Y)$

$2)$ $H(X|Y,Z)\le H(X,Y)$

$3)$ $H(X,Y,Z)+H(Y)\le H(X,Y)+H(Y,Z)$

I have proved the third one, but it is based on part 1.

Should I break them down into summations or should I have to use basic properties of entropy such as the chain rule?

$\endgroup$
1
  • $\begingroup$ You are missing a right "$" on the third inequality I think. $\endgroup$
    – Vim
    Feb 2, 2015 at 15:11

2 Answers 2

1
$\begingroup$

On the left side you have:

$$H(X,Y,Z) +H(Y)= 2 H(Y) + H(X,Z|Y)$$

And on the right:

$$H(X,Y) +H(Y,Z) = H(X|Y) +H(Y) + H(Z|Y) +H(Y) $$

But $H(X,Z|Y) \le H(X|Y) + H(Z|Y)$ - just a conditioned version of the property $H(A,B) \le H(A)+H(B)$

$\endgroup$
0
$\begingroup$

There are many ways to do this. Probably the shortest argument is through definition of mutual information which is $\geq 0$. Then the first follows from the definition of conditional mutual information. $$ H(X|Y,Z) = H(X|Y) - I(X;Z|Y) $$ which implies (1) and (1) implies (2) by definition of chain rule.

Another way to show (1) is with chain rule inequality \begin{align} H(X_1,\ldots,X_n) = \sum_{i=1}^{n} H(X_i|X_{1},\ldots,X_{i-1}) \leq \sum_{i=1}^n H(X_i) \end{align} i.e. (you can think of this as sum of entropy given everything you seen before) $$ H(X,Y,Z)=H(X)+H(Y|X)+H(Z|Y,X)$$

and

\begin{align} H(X,Y|Z) &= E[-\log P(X,Y|Z)] \\ &= E[-\log P(X|Y,Z)P(Y|Z)] \\ &= E[-\log P(X|Y,Z)] + E[-\log P(Y|Z)] \\ &= H(X|Y,Z) + H(Y|Z) \end{align} Convince yourself that $$ H(X|Y,Z)=H(X,Y|Z)-H(Y|Z)=H(X,Z|Y)-H(Z|Y) $$

Then we have $$ H(X|Y,Z)=H(X,Z|Y)-H(Z|Y)\leq H(X|Y)+H(Z|Y)-H(Z|Y) = H(X|Y) \leq H(X,Y) $$

$\endgroup$
8
  • $\begingroup$ what do you mean by I in the first equation? $\endgroup$ Feb 2, 2015 at 17:16
  • $\begingroup$ That is the notation for mutual information wiki $\endgroup$
    – shunjie
    Feb 2, 2015 at 17:27
  • $\begingroup$ how is H(X|Y,Z)=H(X,Y|Z)−H(Y|Z), true? I get that it equals H(x,y,z)-H(y|z)-H(z). Can you show where you are getting these equations from? Im not attacking, I am just very confused $\endgroup$ Feb 3, 2015 at 21:07
  • $\begingroup$ No problem, I updated and made some correction. Hopefully, its better now :) $\endgroup$
    – shunjie
    Feb 3, 2015 at 23:46
  • $\begingroup$ could you use better notation in your sums, because I dont really see how it all comes together? I thought I had it. Your logic makes sense, just I dont see the sums that your using. $\endgroup$ Feb 4, 2015 at 16:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .