MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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 will address what you meant to ask. – KConrad Nov 6 '10 at 17:37
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. – Michael Hardy Nov 6 '10 at 18:06
@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? – skypemesm Nov 6 '10 at 20:39

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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