4
$\begingroup$

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

Improve this question
$\endgroup$
10
  • $\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, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 15:14

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 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, 2014 at 12:42
0
$\begingroup$

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

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

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.