6
$\begingroup$

How does one find the maximum entropy joint distribution of two random variables X and Y given their marginal probability mass functions?

I know:

  • I have the marginals, meaning p(x) and p(y) are fixed.
  • The entropy is maximized when the distribution is even (p(x,y) = 1/n for all x,y), but it can't be even due to the marginals.
  • The joint distribution is only the product of the marginals when X and Y are independent.
  • The KL Divergence looks handy, but I can't use it to prove independence (zero mutual info) if I only know the marginals.

Does anyone know what I'm missing?

$\endgroup$
  • $\begingroup$ Hint: $H(Y|X) \le H(Y)$ with equality if $X$ and $Y$ are independent. $\endgroup$ – leonbloy Sep 17 '13 at 21:19
  • $\begingroup$ @leonbloy That makes total sense. The conditional entropy is maximized when they're independent. And... I don't see any reason given the way the problem was stated to not just make them independent. I just need to make a link between the conditional entropy and P(xy). $\endgroup$ – user1399747 Sep 18 '13 at 0:38
3
$\begingroup$

We know that $H(Y|X) \le H(Y)$ with equality iff $X$ and $Y$ are independent. (This is a consequence of $I(X;Y) \ge 0$ which is a consequence of $D(p(X,Y) || p(X) p(Y)) \ge 0$ which is a consequence of Jensen's inequality; see eg. Cover and Thomas, theorem 2.6.5)

This implies $H(X,Y) \le H(X) + H(Y)$ with equality iff $X$ and $Y$ are independent (another basic result).

In our problem, $H(X)$ and $H(Y)$ are fixed, so the joint entropy is bounded by the above, and that bound is attained (only) if $X$ and $Y$ are independent , i.e. $P(X,Y) = P(X) P(Y)$. Hence, this is the joint probability that maximizes the joint entropy.

$\endgroup$
  • $\begingroup$ I just came to the same conclusion thanks to your hint, though you explained the solution quite a bit better :D Thank you! $\endgroup$ – user1399747 Sep 18 '13 at 1:22
  • $\begingroup$ What is $D()$ in your notation? $\endgroup$ – Daniel May 7 '14 at 22:29
  • $\begingroup$ @Daniel Kullback–Leibler divergence (or distance) (or relative entropy).en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence $\endgroup$ – leonbloy May 8 '14 at 0:21
  • $\begingroup$ @leonbloy, I suppose you meant $D(p(X,Y)||p(X)p(Y))\geq 0$! :) $\endgroup$ – Cupitor Jul 13 '14 at 12:02
  • 1
    $\begingroup$ @Cupitor of course! fixed, thanks $\endgroup$ – leonbloy Jul 13 '14 at 12:57

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.