8
$\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$
2
  • $\begingroup$ Hint: $H(Y|X) \le H(Y)$ with equality if $X$ and $Y$ are independent. $\endgroup$
    – leonbloy
    Commented Sep 17, 2013 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$ Commented Sep 18, 2013 at 0:38

1 Answer 1

6
$\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$
5
  • $\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$ Commented Sep 18, 2013 at 1:22
  • $\begingroup$ What is $D()$ in your notation? $\endgroup$
    – Daniel
    Commented May 7, 2014 at 22:29
  • $\begingroup$ @Daniel Kullback–Leibler divergence (or distance) (or relative entropy).en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence $\endgroup$
    – leonbloy
    Commented May 8, 2014 at 0:21
  • $\begingroup$ @leonbloy, I suppose you meant $D(p(X,Y)||p(X)p(Y))\geq 0$! :) $\endgroup$
    – Cupitor
    Commented Jul 13, 2014 at 12:02
  • 1
    $\begingroup$ @Cupitor of course! fixed, thanks $\endgroup$
    – leonbloy
    Commented Jul 13, 2014 at 12:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .