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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .