How to prove H(X,Y) $\ge$ H(Z)?

Question

I'm solving a problem from elements of information theory, 2nd.

I got stuck by question(c) and actually, I've checked the answer, here it is:

How to prove the inequality from the answer that is H(X,Y) $\ge$ H(Z)? Thanks in advance.

Answer 1

Actually, the inequality $H(Z) \le H(X,Y) $ is immediate, because the variable $Z$ is a function of the (multivariate) variable $(X,Y)$, and you should know that for any random variable $W$ we have $H(g(W))\le H(W)$.

The later is an intuitively obvious property (applying a deterministic function to a $W$ cannot increase the information that $W$ alone gives us ; it can perhaps decrease it, if the function is not one-to-one)

To prove it, consider $U=g(W)$ , and use $$H(U,W)=H(W) + H(U|W) = H(U) + H(W|U)$$ See that $$H(U|W)=H(g(W)|W)=0$$ (to know $W$ is to know $g(W)$), and $$H(W|U) \ge 0$$

hence $$H(U) =H(g(W))\le H(W)$$

Answer 2

I think this can be a proof.

$$H(Z) = \sum_{z\in Z}p(z)\log p(z) = -\sum_{z\in Z}\sum_{x\in X}p(x,z)\log p(z)$$

$$H(X) = -\sum_{x\in X}\sum_{z\in Z} p(x,z)\log p(x)$$

$$\implies H(Z)-H(X) = -\sum_{x\in X}\sum_{z\in Z} p(x,z)\log\frac{p(z)}{p(x)}$$

$$= -\sum_{x\in X}\sum_{z\in Z} p(z|x)p(X=x)\log \frac{p(Z=z)}{p(x)} $$

$$= -\sum_{x\in X}\sum_{z\in Z} p(z|x)p(X=x)\log p(Z=z|x)$$ $$= -\sum_{x\in X}\sum_{z\in Z} p(Z=x+y|x)p(X=x)\log p(Z=z|x)$$ $$= -\sum_{x\in X}\sum_{y\in Y} p(Y=y|X=x)p(X=x)\log p(Z=z|x)$$ $$= -\sum_{x\in X}\sum_{y\in Y} p(x,y)\log \frac{p(z)}{p(x)}$$ $$p(z|x)\ge p(y|x)\quad\text{(achieve equality when independent)}$$ $$\implies -\sum_{x\in X}\sum_{y\in Y} p(x,y)\log p(y|x) \ge -\sum_{x\in X}\sum_{y\in Y} p(x,y)\log \frac{p(z)}{p(x)}$$ $$\implies H(X,Y)-H(X) \ge H(Z)-H(X)$$ $$\implies H(X,Y) \ge H(Z)$$

Author's original response:

I don't know how to use latex and just scan it. Answerer's original image below: