Concentration of functional of Gaussian random variable

Question

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.

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} $