Suppose I have two Gaussian distributions $p(x) = \frac{1}{(2\pi)^{d/2}|\Sigma_p|^{1/2}}\exp(-\frac{1}{2}x^\top \Sigma_p^{-1} x)$ and $q(x) = \frac{1}{(2\pi)^{d/2}|\Sigma_q|^{1/2}}\exp(-\frac{1}{2}x^\top \Sigma_q^{-1} x)$.

The ratio between them is defined as $r(x) = \frac{p(x)}{q(x)} = \frac{|\Sigma_q|^{1/2}}{|\Sigma_p|^{1/2}}\exp(-\frac{1}{2}x^\top (\Sigma_p^{-1} - \Sigma_q^{-1})x)$.

We can see that $E_{x \sim q(x)}[\exp(-\frac{1}{2}x^\top (\Sigma_p^{-1} - \Sigma_q^{-1})x)]= \frac{|\Sigma_p|^{1/2}}{|\Sigma_q|^{1/2}}$.

Now I want to approximate the expectation using sample averages, that is given $n$ i.i.d samples $\{x_i\}_{i=1}^{n}$ from $q(x)$, I want to get the concentration inequality for $ P\Big(\big|\frac{1}{n}\sum_{i=1}^n\exp(-\frac{1}{2}x_i^\top (\Sigma_p^{-1} - \Sigma_q^{-1})x_i) - \frac{|\Sigma_p|^{1/2}}{|\Sigma_q|^{1/2}}\big|\geq t\Big) \leq ? $

I'm willing to assume that $\|\Sigma_p\|_{\max}$, $\|\Sigma_q\|_{\max}$ is bounded where $\|\cdot\|_{\max}$ is the largest element in absolute value. And furthermore, we can assume that $\|\Sigma_p^{-1} - \Sigma_q^{-1}\|_1$ is bounded, where $\|\cdot\|_1$ is the sum of absolute values.

  • $\begingroup$ What was the point of defining $r(x)$? $\endgroup$
    – S.B.
    Commented Aug 11, 2016 at 14:39

1 Answer 1


You may use the Chebyshev inequality for the calculation of that probability:

$P(|X-E[X]|\geq a) \leq \frac{Var(X)}{a^2} $

So as $E_{q(x)}[\frac{1}{n}\sum_{i=1}^ne^{\frac{-1}{2}x^T(\Sigma_p^{-1} - \Sigma_q^{-1})x}] = \frac{|\Sigma_p|^{\frac{1}{2}}}{|\Sigma_q|^{\frac{1}{2}}}$ then you can calculate your concentration inequality as:

$P\left(|\frac{1}{n}\sum_{i=1}^ne^{\frac{-1}{2}x^T(\Sigma_p^{-1} - \Sigma_q^{-1})x}| - \frac{|\Sigma_p|^{\frac{1}{2}}}{|\Sigma_q|^{\frac{1}{2}}} \geq t\right) \leq \frac{Var\left(e^{\frac{-1}{2}x^T(\Sigma_p^{-1} - \Sigma_q^{-1})x}\right)}{t^2} $

  • $\begingroup$ function may not have 2nd moment, as is easily seen in 1d $\endgroup$
    – user83457
    Commented Oct 10, 2016 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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