# How to prove the following entropy formula?

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!

-
It's the same as $H(X,Y) = H(X) + H(Y|X)$, all conditioned on $Z$. – leonbloy Feb 12 '13 at 12:49
Okay, thank you :) – jjepsuomi Feb 12 '13 at 12:52

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*}

-
Thanx a million! =) – jjepsuomi Feb 12 '13 at 13:37
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? – jjepsuomi Feb 12 '13 at 13:50

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.

-