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.

I am trying to find a bound for variance of an arbitrary distribution $f_Y$ given a bound of a Kullback-Leiber divergence from a zero-mean Gaussian to $f_Y$, as I've explained in this related question. From page 10 of this article, it seems to me that:

$$\frac{1}{2}\left(\int_{-\infty}^{\infty}|p_Z(x)-p_Y(x)|dx\right)^2 \leq D(p_Z\|p_Y)$$

I have two questions:

1) How does this come about? The LHS is somehow related to total variation distance, which is $\sup\left\{|\int_A f_X(x)dx-\int_A f_Y(x)dx|:A \subset \mathbb{R}\right\}$ according to wikipedia article, but I don't see a connection. Can someone elucidate?

2) Section 6 on page 10 of the same article seems to talk about variation bounds, but I can't understand it... Can someone "translate" that to the language that someone with a graduate-level course on probability can understand? (I haven't taken measure theory, unfortunately.)

share|improve this question
1  
Hint for (1): Consider the set $A = \{x: f_X(x) \leq f_Y(x)\}$. –  cardinal Oct 2 '11 at 1:30
1  
@cardinal (sorry for the delay) Using your hint I've been able to equate $\mathcal{L}_1$ distance with double of total variation as follows: $$\begin{align}\int_{-\infty}^\infty |f_Z(x)-f_Y(x)|dx&=\int_A f_Z(x)-f_Y(x) dx+\int_{A^c} f_Y(x)-f_Z(x) dx\\ &=\int_A f_Z(x)dx-\int_A f_Y(x) dx+\int_{A^c} f_Y(x)dx-\int_{A^c}f_Z(x) dx\\&=\int_A f_Z(x)dx-\int_A f_Y(x) dx+1-\int_A f_Y(x)dx-1+\int_Af_Z(x) dx\\ &=2\left(\int_A f_Z(x) dx-\int_A f_Y(x) dx\right)\end{align}$$ and obviously set $A$ yields the supremum in total variation. However, I can't quite connect this to KL divergence... –  M.B.M. Oct 12 '11 at 23:48

1 Answer 1

up vote 2 down vote accepted

1) Check out Lemma 11.6.1 in Elements of Information Theory by Thomas and Cover.

2) The LHS is essentially the total variation between probability measures $p_Z$ and $p_Y$ (see here). I think "variation bounds" quite literally means bounds on the total variation between the probability measures, as given in the Lemma on p. 11.

share|improve this answer

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.