Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $p(x)$ be a fixed distribution over a discrete space.

Let $A, C > 0$ be constants. Let $\epsilon > 0$. Can we find an example of a distribution $q_{\epsilon}$ such that $\mathrm{KL}(p||q_{\epsilon}) < \epsilon$, but $E[(\log (p(x)/q_\epsilon(x)))^2] \ge A * \epsilon^C$?

$q_{\epsilon}$ should be geometric, if possible (in which case, the discrete space is the natural numbers).

Perhaps I could also get a clue if I knew whether there is a name for the quantity $E[(\log (p(x)/q_\epsilon(x)))^2]$.

All expectations are taken with respect to $p$. So, for example,

$E[(\log (p(x)/q_\epsilon(x)))^2] = \sum_x p(x) \left(\log (p(x)/q_\epsilon(x))\right)^2$

and

$\mathrm{KL}(p||q_{\epsilon}) = \sum_x p(x) \log \frac{p(x)}{q_{\epsilon}(x)}$

I think that the only chance of solving this is by creating a $q_\epsilon$ such that $\log(p/q_\epsilon)$ is either extremely negative or extremely positive. Then, when taking the squares, it would diverge. But I don't see how this could happen when the KL divergence is smaller than $\epsilon$, because, for example, when the KL divergence is exactly 0, $p(x)=q_{\epsilon}(x)$ for all $x$, and we could not have this effect of $\log p(x)/q(x)$ being extremely small or big.

I think I can show that for the geometric case, unfortunately, there is no such construction, but I am not sure. I would be okay with other examples, as long as the space is discrete.

share|improve this question
    
$p(x)$ can be part of the construction, not just $q_{\epsilon}(x)$. –  rasper Oct 13 '10 at 14:00
    
Second moment does not necessarily exist in the first place. So yes, you can find such p and q with arbitrary large A. For example take p to be geometric upto some large $N$ and then $1\over n^3$. $q$ is geometric. Thus as $N\to\infty$ $KL(p||q_\epsilon)\to0$, but the second moment is always $+\infty$ (if you don't like this, cut $p$ at $M\gg N$. –  Paul Yuryev Oct 13 '10 at 17:12
    
Thanks. That's an interesting case, but does not follow the requirements: $p$ needs to be fixed. It is $q$ that can change depending on $\epsilon$. –  rasper Oct 13 '10 at 21:54
    
Maybe my wording is not clear. The quantifiers are: Exists P such that For All eps,C,A Exists q_eps such that KL < eps and second moment >= C*eps^A –  rasper Oct 13 '10 at 21:56
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.