3
$\begingroup$

I think this must be so because of how Mutual Information is defined. The formula is

$$ I = \sum_{x,y} [p(x,y) \log(p(x,y)) - p(x,y)\log(p(x)p(y))] $$

This is apparently $\ge0$. I can understand it equals 0 when $X$ and $Y$ are independent, and that its maximum is $H(X)$ (if $Y=X$). And I know the $\ge0$ result can be proven with Gibb's inequality.
But I'm curious as to how $\sum_{x,y} p(x,y) \log(P(x)P(y))$ behaves as they become more dependant. Because $I$'s lowest point is $0$ I guess that as they become more dependant it must decrease. But I can't see a way to frame the problem so as to find an answer to the question why it can only decrease as they become more dependant.

edit: I've now done multiple edits where I changed increase/decrease. To be clear $- p(x,y)\log(p(x)p(y))$ increases, $p(x,y)\log(p(x)p(y))$ decreases.

$\endgroup$
3
$\begingroup$

The quantity you're interested in is the negative of the cross entropy between the joint distribution and the product of the marginal distributions:

$$H(p(x,y), p(x) p(y)) = -\sum_{x,y} p(x,y) \log(p(x) p(y))$$

Here's an explanation of why it must decrease as $X$ and $Y$ become more dependent, assuming we hold the joint entropy constant:

We can measure the dependence between $X$ and $Y$ using the mutual information, which is defined as the KL divergence between the joint distribution and the product of the marginal distributions. That is, it measures how different the true joint distribution is from what it would be if $X$ and $Y$ were independent:

$$I(X,Y) = D_{KL}(p(x,y) \parallel p(x) p(y))$$

The KL divergence $D_{KL}(P \parallel Q)$ is equal to the difference between the cross entropy $H(P,Q)$ and the entropy $H(P)$, so:

$$I(X,Y) = H(p(x,y), p(x) p(y)) - H(p(x,y))$$

Let's consider two possible joint distributions $p_0(x,y)$ and $p_1(x,y)$, where the mutual information between $X$ and $Y$ is higher for $p_1$ than for $p_0$. Writing out the mutual information for both cases, we have:

$$H(p_1(x,y), p(x) p(y)) - H(p_1(x,y)) > H(p_0(x,y), p(x) p(y)) - H(p_0(x,y))$$

Assume that the joint entropy is held fixed, so $H(p_0(x,y)) = H(p_1(x,y))$. In that case, these terms cancel out, and we're left with:

$$H(p_1(x,y), p(x) p(y)) > H(p_0(x,y), p(x) p(y))$$

Therefore, assuming the joint entropy is constant, the cross entropy between the joint distribution and the product of the marginal distributions increases as the mutual information between $X$ and $Y$ increases. The quantity you're interested in (the negative cross entropy) therefore decreases.

$\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.