Let $X = (X_1,\ldots,X_n) \in \mathbb{R}^n$ be jointly Gaussian with mean $0$, covariance matrix: $Var(X_i) = 1$, $Cov(X_i, X_{i+1}) = -1/2$, and $Cov(X_i, X_j) = 0$ else.

Let $\zeta \in \mathbb{R}^n$ be a fixed vector, $\zeta_i > 0$ for all $i$. I want a tight lower bound on $P(X < \zeta)$, that is,

$$ P(X_1 \leq \zeta_1, \ldots, X_n \leq \zeta_n) \geq ? $$

In particular, I'm interested in the case where the $\zeta_i$'s are i.i.d $exp(1)$.

One rather loose bound when the $\zeta_i$'s are far apart is $$ P(X_1 \leq \zeta_1, \ldots, X_n \leq \zeta_n) \geq P(\max_iX_i \leq \min_j\zeta_j) $$ and from there one can lower bound this further with Sudakov.

Due to the negative correlation we can't apply Slepian's lemma directly (and the high negative correlation would probably give us a bad bound).

I've looked into the multivariate Mills ratio literature, but they seem to be concerned with bounding $$ P(X_i \geq \zeta_i) $$ for $\zeta_i > 0$

I've also tried writing down the integral and the inverse covariance matrix explicitly. (Since the covariance matrix $\Sigma$ in this case is a triangular circulant matrix, the inverse can be found in closed form, but it's not sparse and rather complicated).

Any ideas would be highly appreciated. This has applications in ranking and statistics.



3 Answers 3


This is not a full answer but, first, to point out that things are probably simpler for random than for deterministic $\zeta_i$s. If the $\zeta_i$ are i.i.d. exponential with parameter $1$, for every real numbers $x_i$, $$ P[\zeta_1\ge x_1,\ldots,\zeta_n\ge x_n]=\exp(-[x_1^++\cdots+x_n^+]), $$ where $x^+=x$ if $x\ge0$ and $0$ otherwise. Hence, $$ (*)=P[\zeta_1\ge X_1,\ldots,\zeta_n\ge X_n]=E[\exp(-[X_1^++\cdots+X_n^+])]. $$ A second step (certainly not optimal) is that, the exponential being convex, by Jensen's inequality, $$ (*)\ge\exp(-E[X_1^++\cdots+X_n^+])=\exp(-nE[X_1^+])=\exp(-n/\sqrt{2\pi}). $$ Note that the random variables $X_i$ are independent when their indices are at distance at least $2$, hence $$ (*)\le E[\exp(-X_1^+)]^{\lfloor n/2\rfloor}. $$ Another (nonconclusive) remark is that a Gaussian random vector $(X_i)_{1\le i\le n}$ with correlation structure as in the post can be realized with the help of an i.i.d. centered reduced Gaussian random vector $(Y_i)_{1\le i\le n+1}$ as $$ X_i=(Y_i-Y_{i+1})/\sqrt2. $$ Hence, one has also $$ (*)=E[\exp(-[(Y_1-Y_2)^++\cdots+(Y_n-Y_{n+1})^+]/\sqrt2)]. $$


Thanks Didier. The last line you wrote gave me an idea, and I think I managed to get a sharp bound for the i.i.d exp(1) case.

(A minor correction: $X_i = (Y_i - Y_{i+1})/\sqrt{2}$, not $/2$)

Using the bound: $(f+g)^+ \leq f^+ + g^+$, we have $$ (\ast) \geq E(\exp(-1/\sqrt{2}[Y_1^+ + (-Y_2)^+ + Y_2^+ + (-Y_3)^+ + \ldots + (-Y_{n+1})^+])) $$ Note that $(-Y_2)^+ + Y_2^+ = |Y_2|$. Grouping terms, using independence, we have that the RHS is equal to $ (2\exp(1/4)\Phi(-1/\sqrt{2}))^{(n-1)}\cdot (1/2 + \exp(1/4)\Phi(-1/\sqrt{2}))^2$.

But your introduction of the $Y_i$ is super! Thanks!

  • $\begingroup$ Well done. But why sharp? I understand that $E(\exp(-|Y|/\sqrt2))^{n+o(n)}\le(*)\le E(\exp(-Y^+))^{n/2+o(n)}$. $\endgroup$
    – Did
    Commented Apr 22, 2011 at 0:03

Hi, did u try the general version of Slepian's inequality by Li and Shao "A normal comparison inequality and applications"?


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.