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