Lower bound for Gaussian random vector with negative correlation - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T10:25:31Z http://mathoverflow.net/feeds/question/62449 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/62449/lower-bound-for-gaussian-random-vector-with-negative-correlation Lower bound for Gaussian random vector with negative correlation Ngoc Mai Tran 2011-04-20T18:55:13Z 2012-07-11T14:11:35Z <p>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. </p> <p>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 &lt; \zeta)$, that is,</p> <p>$$P(X_1 \leq \zeta_1, \ldots, X_n \leq \zeta_n) \geq ?$$</p> <p>In particular, I'm interested in the case where the $\zeta_i$'s are i.i.d $exp(1)$.</p> <p>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. </p> <p>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). </p> <p>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$</p> <p>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). </p> <p>Any ideas would be highly appreciated. This has applications in ranking and statistics.</p> <p>Ngoc</p> http://mathoverflow.net/questions/62449/lower-bound-for-gaussian-random-vector-with-negative-correlation/62455#62455 Answer by Didier Piau for Lower bound for Gaussian random vector with negative correlation Didier Piau 2011-04-20T20:10:07Z 2011-04-21T23:57:44Z <p>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)].$$</p> http://mathoverflow.net/questions/62449/lower-bound-for-gaussian-random-vector-with-negative-correlation/62587#62587 Answer by Ngoc Mai Tran for Lower bound for Gaussian random vector with negative correlation Ngoc Mai Tran 2011-04-21T23:34:51Z 2011-04-21T23:34:51Z <p>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. </p> <p>(A minor correction: $X_i = (Y_i - Y_{i+1})/\sqrt{2}$, not $/2$) </p> <p>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$. </p> <p>But your introduction of the $Y_i$ is super! Thanks!</p> http://mathoverflow.net/questions/62449/lower-bound-for-gaussian-random-vector-with-negative-correlation/101956#101956 Answer by pgviethung for Lower bound for Gaussian random vector with negative correlation pgviethung 2012-07-11T14:11:35Z 2012-07-11T14:11:35Z <p>Hi, did u try the general version of Slepian's inequality by Li and Shao "A normal comparison inequality and applications"?</p>