1
$\begingroup$

How can we figure out the combination of probability mass functions p and q, such that the relative entropy $D(p||q) = \sum p \log \frac{p}{q}$ is maximum? Of course this is a convex function.

I am looking for something like 'if q is uniform, we have maximum RE for all p'. Any ideas?

$\endgroup$
3
  • $\begingroup$ What are your constraints on the probability distributions you are looking at? Do you want them to be closed under convex linear combinations or something else? If you're not going to say there are any actual constraints then I don't see how the question can be answered. (If, for instance, we limit our universe to one pair of probability distributions p and q, the answer is quite different than if we imposed some kind of constraints that would be natural.) Perhaps something in section 6 of math.uconn.edu/~kconrad/blurbs/analysis/entropypost.pdf will address what you meant to ask. $\endgroup$
    – KConrad
    Nov 6, 2010 at 17:37
  • $\begingroup$ Don't you want a minus sign in front of "log" if you write it in that form? If there are no constraints on $p$, I think the value of $p$ that would maximize $D$ with $q$ fixed is just $q$ itself. $\endgroup$ Nov 6, 2010 at 18:06
  • $\begingroup$ @KConrad: Yes we can say that p and q are both positive and real-valued in the interval (0,1]. Additionally we can say that they are closed under convex linear combinations. How can we approach this problem? Can we apply any other constraint in order to consider only finite-valued relative entropy? $\endgroup$
    – skypemesm
    Nov 6, 2010 at 20:39

1 Answer 1

1
$\begingroup$

Say $p$ and $q$ are distributions on a finite set $\mathcal{X}$. If $p$ and $q$ are singletons on different values $x$ and $x'$, say, then $D(p \| q) = \infty$. So I assume you want to rule that out.

So let's say $p$ and $q$ must have mass on all elements of $\mathcal{X}$. In this case, as KConrad says, you want to impose some structure on the set of $p$ and $q$. Even in this case, I don't think you can find a unique $q$ that is maximizing for all $p$. Suppose further that $p$ and $q$ have to lie in some convex polytope $K$ of distribuions. Since the relative entropy is convex in $p$ and $q$, for fixed $p$ the maximizing $q$ is a vertex/extreme point of $k$, and vice versa. So the vertices $\{v_i\}$ of $K$ partition $K$ into sets $P_i$ such that if $p \in P_i$ then $q = v_i$ maximizes $D(p \| q)$. Similarly, there is another partition $Q_i$ such that if $q \in Q_i$ then $p = v_i$ maximizes $D(p \| q)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.