Estimate on gaussian distribution

Let X be an $\mathbb R^d$-valued random variable with distribution $N_d(0,\Sigma)$. I'm looking for a function $f$ such that $$P(|X_1|\leq M, |X_2|\leq M,\dots, |X_d|\leq M)\geq f(M),$$ and such that $f(M)\to 1$ as $M\to\infty$ (i.e. giving the convergence rate of that probability to 1). Of course $f$ will somehow depend on $\Sigma$ (most certainly on its rank, maybe on its norm defined in some way). I tried to connect it to the trivial case $\Sigma=I_d$ but with no success so far. Do you have any ideas?

EDIT: of course an idea is to use $x'\Sigma^{-1}x\leq |x|^2/\lambda_1$ (where $\lambda_1$ is the lowest eigenvalue of $\Sigma$) and then use a bound on the standard normal. But again this requires invertibility of $\Sigma$, and I don't want to assume that. When the rank of $\Sigma$ is lower than $d$, another idea I had was to write the last $n-d$ components of $X$ as linear combinations of the other ones, but I'm still unable to simplify the expressions enough to obtain simple convergence rates in terms of some basic properties of $\Sigma$.

-
$f(M)=(2\pi)^{-d/2}||\Sigma||^{-1/2}\int_{-M}^{M}\cdots\int_{-M}^{M}\exp\large(-‌​\frac{1}{2}x\cdot\Sigma^{-1}\cdot x\large)dx_1dx_2\cdots dx_d$ – Carlo Beenakker Jan 25 '14 at 22:36
not feasible if the rank of the matrix is lower than $d$, which was the main point of the question – splinter123 Jan 25 '14 at 23:39
Here is a basic schematic: Find the maximal ellipsoid of the form $\mathcal E_r = \{x: x^T \Sigma^{-1} x \leq r^2\}$ that is inscribed in the hypercube $[-M,M]^d$. The correct $r$ is something like $M/\sigma_1$ where $\sigma_1 = \max_i \sqrt{\Sigma_{ii}}$. This gives a lower bound for your probability in terms of the probability that the norm of a $d$-dimensional standard normal falls within the given radius. This latter quantity can be bounded using a Chernoff bound giving something like $f(M) = 1 - b M^{d/2} \exp(-M/2)$ for constant $b$ (likely, $b = d^{-d/2}\exp(d/2)$ or so). – cardinal Jan 26 '14 at 3:42
yes of course I can use $x'\Sigma^{-1}x\leq |x|^2/\lambda_1$ (where $\lambda_1$ is the lowest eigenvalue of $\Sigma$) and then use a bound on the standard normal. But again this requires invertibility of $\Sigma$, and I don't want to assume that! – splinter123 Jan 26 '14 at 8:13
Perhaps you can take a moment to reread my comment with additional care. I mention nothing about eigenvalues and the argument is readily adaptable to the nonsingular case. (The handling of the lack of inverse should take only a slight amount of care by using the SVD.) – cardinal Jan 26 '14 at 15:14

A general approach to obtain upper and lower bounds on $P(|X_1|\leq M_1, |X_2|\leq M_2,\dots, |X_d|\leq M_d)$ for a singular multivariate Gaussian, with a noninvertible covariance matrix, is developed by Genz and Kwong, Numerical Evaluation of Singular Multivariate Normal Distributions. The upper and lower bounds are expressed in terms of cumulative distributions of a nonsingular Gaussian, which can then be evaluated numerically with high accuracy.

-
Thanks, that seems to treat well the singularity issue. The procedure still requires numerical computation, and does not exhibit a simple bound f(d,M) allowing to guess a convergence rate... but I might be able to get that by using some metric on the cholesky matrix. – splinter123 Jan 27 '14 at 12:42

Based on Carlo's contribution, after short manipulations I got to the answer $$f(M)=\left(1-\exp\left(-\frac{M^2}{d^2 \|C\|^2}\right)\right)^d,$$ for the full rank case, where $\|C\|=\max |C_{ij}|$ and $C$ is the Cholesky factor of $\Sigma$.

When $\Sigma$ is of rank $k<d$, the first step is to perform the SVD $\Sigma=R\Lambda R'$, and then define $C=R\Lambda^{1/2}Q'$, where $Q$ is an orthogonal matrix such that $C$ is lower triangular. Then the same $f$ can be used with this new $C$ and with $d$ replaced by $k$ (so that convergence is faster when the rank is lower, for equal $\|C\|$).

Now since in any case $\|C\|\leq \sqrt{\max_{i} \Sigma_{ii}}=:\bar\Sigma$, we can sum up both cases by writing $$f(M)=\left(1-\exp\left(-\frac{M^2}{k^2 \bar\Sigma^2}\right)\right)^k.$$

-
Note that a simple application of the union bound will yield a much stronger $f(M)$ for every moderately large $M$, namely, $\tilde f(M) = 1 - 2d\mathbb P(Z > M/\bar\Sigma)$ where $Z$ is standard normal. – cardinal Jan 31 '14 at 1:48
...or much weaker when the rank is lower than $d$. – splinter123 Jan 31 '14 at 8:42
No. You have $k^{-2}$ stuck in the exponent. – cardinal Jan 31 '14 at 11:15
and so what? Take a very big matrix with a very small rank (which is not that rare in applications) and you'll see the advantage – splinter123 Jan 31 '14 at 13:03