An inequality for Shannon's entropies

146 Views Asked by At

This question concerns Shannon's entropy of discrete random variables.

I want to show $H(X,Y)+H(Y,Z)-H(Y) \geq H(X,Z)$

On the left, we have $-\sum_{x,y}p(x,y) \log p(x,y) -\sum_{y,z}p(y,z) \log p(y,z)+\sum_{y}p(y) \log p(y) \\ =-\sum_{x,y,z}p(x,y,z) \log (\frac{p(x,y)p(y,z)}{p(y)})=-\sum_{x,y,z}p(x,y,z) \log [p(x|y)p(y,z)]$

(where $p(x,y,z)$ is the joint probability distribution of $X,Y,Z$)

On the right $\sum_{x,y,z}p(x,y,z) \log p(x,z)$

1

There are 1 best solutions below

0
On BEST ANSWER

A comment on your approach: for these type of inequalities, it is rarely, if ever, useful to expand the entropies in terms of probabilities. Instead, the typical tools are the chain rule of entropy, and some basic positivity statements (more generally, some kind of submodularity). These are called Shannon-type inequalities, and R. Yeung has some nice work on this that you might want to read. In addition, a standard text like Cover and Thomas will have enough problems to give you some intuition about how to go about proving such things.


For the question itself, by subtracting $H(Z)$ from both sides of the inequality, and using the chain rule $H(A,B) = H(A) + H(B|A),$ the stated inequality is equivalent to \begin{align} H(X|Y) + H(Y|Z) \overset{?}\ge H(X|Z).\end{align}

Since conditioning reduces entropy, it holds that $$ H(X|Y) + H(Y|Z) \ge H(X|Y,Z) + H(Y|Z) = H(X,Y|Z).$$

But $$H(X,Y|Z) = H(X|Z) + H(Y|X,Z) \ge H(X|Z)$$ since entropies are non-negative, and we're done.

This also tells us when equality will hold: If and only if $H(X|Y) = H(X|Y,Z)$ and $H(Y|X,Z) = 0$. The first says that $X$ and $Z$ are conditionally independent given $Y$, and the second says that $Y$ is a deterministic function of $X$ and $Z$.