0
$\begingroup$

Could anyone show me a proof or redirect to a source where the following entropy equation is proved? =)

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

Thank you!

$\endgroup$
  • 1
    $\begingroup$ It's the same as $H(X,Y) = H(X) + H(Y|X)$, all conditioned on $Z$. $\endgroup$ – leonbloy Feb 12 '13 at 12:49
2
$\begingroup$

The closely-related identity $H(X,Y) = H(X) + H(Y|X)$ should certainly be in any text on information theory (even if the one you ask for specifically is not).

But let's do it anyway, step-by-step. I'll assume $X$, $Y$, and $Z$ are all discrete variables. The brute-force way of proving such a relation is to break down the definition of the entropy. It's pretty mechanical so long as you recall that $p(x,y|z) = p(y|x,z)p(x|z)$.

$\begin{align*} H(X,Y|Z) &= -\sum_{x,y} p(x,y|z) \log p(x,y|z) \\ &= -\sum_{x,y} p(x,y|z) \log p(y|x,z) - \sum_{x,y} p(x,y|z) \log p(x|z) \\ &= -\sum_{x,y} p(x,y|z) \log p(y|x,z) - \sum_{x} p(x|z) \log p(x|z) \\ &= -\sum_{x,y} p(y|x,z)p(x|z) \log p(y|x,z) + H(X|Z) \\ &= -\sum_{x} \left[\sum_{y} p(y|x,z) \log p(y|x,z)\right]p(x|z) + H(X|Z) \\ &= \sum_{x} H(Y|X=x,Z)p(x|z) + H(X|Z) \\ &= H(Y|X,Z) + H(X|Z) \end{align*} $

$\endgroup$
  • $\begingroup$ Thanx a million! =) $\endgroup$ – jjepsuomi Feb 12 '13 at 13:37
  • $\begingroup$ By the way...could you derive the formula $p(x,y|z)=p(y|x,z)p(x|z)$? I know conditional probability definition but this notation confuses me a bit...I have had troubles with this before :/ I know that $P(A|B) = P(A,B)/P(B)$, but $p(x,y|z)=p(y|x,z)p(x|z)$ confuses me for some reason. Does $p(x,y|z)=p(y|x,z)p(x|z)$ mean: "The probability of X and Y given Z = probability of Y given X and Z times the probability of X given Z? $\endgroup$ – jjepsuomi Feb 12 '13 at 13:50
0
$\begingroup$

An illuminating way of proving this is to use conditional information functions.

Define three functions using conditional probabilities.

$f_1(x,y,z) = - \log P(X = x, Y = y | Z = z)$

$f_2(x,y,z) = - \log P(X = x | Z = z)$

$f_3(x,y,z) = - \log P(Y = y | X = x, Z = z)$

Let $W_i = f_i(X,Y,Z)$ for $i= 1,2,3$. Notice that $W_1, W_2, W_3$ are a.e. defined, hence legit random variables and that $W_1 = W_2 + W_3$ holds. Integrating both sides gives the desired equality.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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