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

  • $\begingroup$ $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$ $\endgroup$ – Carlo Beenakker Jan 25 '14 at 22:36
  • $\begingroup$ not feasible if the rank of the matrix is lower than $d$, which was the main point of the question $\endgroup$ – splinter123 Jan 25 '14 at 23:39
  • $\begingroup$ 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). $\endgroup$ – cardinal Jan 26 '14 at 3:42
  • $\begingroup$ 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! $\endgroup$ – splinter123 Jan 26 '14 at 8:13
  • $\begingroup$ 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.) $\endgroup$ – 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.

  • 1
    $\begingroup$ 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. $\endgroup$ – 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.$$

  • $\begingroup$ 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. $\endgroup$ – cardinal Jan 31 '14 at 1:48
  • $\begingroup$ ...or much weaker when the rank is lower than $d$. $\endgroup$ – splinter123 Jan 31 '14 at 8:42
  • $\begingroup$ No. You have $k^{-2}$ stuck in the exponent. $\endgroup$ – cardinal Jan 31 '14 at 11:15
  • $\begingroup$ 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 $\endgroup$ – splinter123 Jan 31 '14 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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