For a standard normal random variable $X \sim \mathcal{N}(0,1)$, we have the simple upper-tail bound of
$$\mathbb{P} (X > x) \leq \frac{1}{x \sqrt{2\pi}} e^{-x^2 / 2}$$
and thus from this we can deduce the general upper-tail bound for $X' \sim \mathcal{N}(\mu, \sigma^2)$ to be
$$\mathbb{P}(X' > x) = \mathbb{P}\left(X > \frac{x – \mu}{\sigma}\right) \leq \frac{\sigma}{(x – \mu)\sqrt{2 \pi}} e^{-(x – \mu)^2/(2\sigma^2)}$$
How can this type of exponential decay bound be generalized to a $d$-dimensional multivariate normal distribution $\vec{X}$ with mean $\vec{\mu}$ and covariance matrix $\Sigma$? Specifically, can we bound the probability
$$\mathbb{P}(\|\vec{X} – \vec{\mu}\| > x)$$
My guess is that we can probably get a a bound that is exponentially small in $x^2$, but how exactly does $\Sigma$ figure in? The more concise the description, the better, e.g. I would prefer a bound that only depends on certain eigenvalues of $\Sigma$ to one that depends on all the entries of $\Sigma$. Even better would be a bound only depending on $\|\Sigma\|$ (for some suitable norm).
I took a look at this post, but my question is simpler as I don't want a bound on each component of my multivariate Gaussian. I suspect there should be a simpler bound (that does not depend on individual matrix elements) to my question than what is given in the answer to the question I linked.
Thanks!
Best Answer
The keywords you are looking for are "Gaussian chaos of order two" or "Hanson-Wright inequality", see for instance Example 2.12 in Concentration Inequalities: A Nonasymptotic Theory of Independence by Gábor Lugosi, Pascal Massart, and Stéphane Boucheron, or Theorem 6.3.2 in the High Dimensional Probability book by Vershynin (the author provides a free pdf version on his website, I believe).
If $\|\cdot\|_F$ and $\|\cdot\|_{op}$ are the Frobenius and Operator norm of matrices, the result says that if $X\sim N(0, \Sigma)$ $$ P( \|X\|^2 \ge trace[\Sigma] + 2 \sqrt{t} \|\Sigma\|_F + 2t\|\Sigma\|_{op} ) \le e^{-t} $$ or equivalently with $Z=\Sigma^{-1/2}X \sim N(0, I)$, $$ P( \|\Sigma^{1/2}Z\|^2 \ge trace[\Sigma] + 2 \sqrt{t} \|\Sigma\|_F + 2t\|\Sigma\|_{op} ) \le e^{-t}. $$ There is also a slightly tighter bound for the lower tail, that can be found in Lemma 1 of Laurent and Massart (2000).