Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $p(x)$ be a fixed distribution.

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(x)))^2] \ge A * \epsilon^C$?

If $p$ and $q_{\epsilon}$ would be a coin toss or a geometric distribution, that would be even better.

I hope I am making myself clear. This is a rather hard question. Perhaps I could also get a clue if someone could tell me whether there is a name for the quantity $E[(\log (p(x)/q(x)))^2]$. (KL divergence is defined as $E[\log (p(x)/q(x))]$.)

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

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

share|improve this question
    
Or... I would be happy with a proof of the opposite case, i.e. KL divergence smaller than $\epsilon$ entails the expected value of $\log p /\log q$ squared is smaller than some polynomial of $\epsilon$. –  normvector Oct 13 '10 at 0:38
    
@rasper: This question needs significant editing. Apart from the potential confusion concerning "two distributions" p and q but q "not fixed" (in what way??) and vagueness with quantifiers (what is the scope of "for all q that satisfy..."??), your definition of KL divergence is incorrect: it's the p-expectation of log(p(x)) - log(q(x)), not of the ratios of the logs. –  whuber Oct 13 '10 at 3:00
1  
you are absolutely right. I edited the question to make it more clear. I was using the right definition of KL divergence when trying to solve it. –  normvector Oct 13 '10 at 11:50
    
@rasper: Thanks. I had hoped that was the case but I wasn't sure. –  whuber Oct 13 '10 at 14:39

1 Answer 1

up vote 2 down vote accepted

The idea is to modify just one term of a distribution $p$ in a way that changes the distribution very little but alters the variance of the log ratio profoundly. In order to make this work, the term that gets modified changes at each step, taking us farther and farther into the tail of $p$, in the hope that this will assure the convergence of the modified distributions to $p$ in the sense of the KL divergence between them going to $0$.

Let $p$ be the geometric distribution

$$\Pr(x) = p(x) = 2^{-x}, x = 1, 2, \ldots$$

and for each $n = 1, 2, \ldots$ let

$$q_n(x) = C_n p(x) \quad \text{if}\quad x \ne n$$ $$= 2^{-f_n} \quad \text{if} \quad x = n$$

where $f_n$ is a sequence of positive real numbers to be determined and $C_n$ is a sequence of normalizing constants. The requirement that $q_n$ be a probability function determines $C_n$:

$$1 = \sum_x {q(x)} = C_n \sum_{x \ne n} {p(x)} + 2^{-f_n} = C_n (\sum_x {p(x)} - p(n)) + 2^{-f_n} $$

$$= C_n (1 - p(n)) + 2^{-f_n} = C_n(1 - 2^{-n}) + 2^{-f_n},$$

whence

$$C_n = (1 - 2^{-f_n}) / (1 - 2^{-n}).$$

We can now compute the KL divergence:

$$\mathrm{KL}(p||q_n) = \sum_x {p(x) \log( p(x) / q_n(x))}.$$

Breaking this into a sum over $x \ne n$ and the remaining term as before gives

$$= \sum_x {p(x) \log(C_n)} - p(n) \log(C_n) + p(n) \log( 2^{-n} / 2^{-f_n} )$$

$$= \log(C_n) \left(1 - p(n) \right) + p(n) \left( f_n - n \right)$$

$$= \log(C_n) \left(1 - 2^{-n} \right) + 2^{-n} \left( f_n - n \right)$$

(using the logarithm base 2 for ease of computation). Notice that the sequence $\log(C_n)$ converges to $0$ provided $f_n$ diverges, so the first summand goes to $0$. To get the whole thing to converge to zero we therefore require that $f_n - n = o(2^n)$; i.e., $f_n$ should not diverge too rapidly.

A similar computation produces the expectation of the squared log ratio:

$$ \sum_x {p(x) ( \log( p(x) / q_n(x)) )^2}$$

$$= \sum_x {p(x) (\log(C_n))^2} - p(n) (\log(C_n))^2 + p(n) \left(\log( 2^{-n} / 2^{-f_n} ) \right)^2$$

$$= (\log(C_n))^2 \left(1 - 2^{-n} \right) + 2^{-n} \left( f_n - n \right)^2 .$$

Again the first summand converges to zero. However, we can choose $f_n$ (subject to the previous restriction not to diverge too quickly) to make the right summand behave almost as we wish. Three regimes are exhibited by these choices:

  1. $f_n = n^2$. The right summand converges to $0$.

  2. $f_n = 2^{n/2} + n$. The right summand equals a constant $1$, converging to $1$.

  3. $f_n = (2^{n/2} + n)n$. The right summand (equal to $n^2$) diverges.

In all cases $f_n - n = o(2^n)$ as required, ensuring that $\mathrm{KL}(p||q_n) \to 0$. Finally, the variance of $\log( p / q )$ behaves like the expectation of $(\log( p/q ))^2$ because the square of the expectation is converging to $0$.

This shows that the asymptotic behavior of the variance of the log ratio is essentially independent of the convergence of $q$ to $p$ in the sense of the KL divergence.

$q$, by the way, is the probability distribution for a simple truncated experiment provided $f_n \ge n$ (which includes all three cases): let $X$ be the number of flips of a fair coin needed to reach heads the first time. If the number of flips is not $n$, accept $X$. Otherwise, only in the case $X = n$, generate a uniform random number $U$. If $U \lt 2^{n - f_n}$, accept the result $X$. Otherwise, re-run the same experiment recursively until eventually some value is accepted.

share|improve this answer
    
I think this is right. I may need to modify this a bit for my needs. Thank you! –  normvector Oct 13 '10 at 15:15

Your Answer

 
discard

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.