# What is the probability that random variable $x_1$ is maximum of random vector $X=(x_i)$ from a multivariate normal distribution?

Given a $n$-dimensional multivariate normal distribution $X=(x_i) \sim \mathcal{N}(\mu, \Sigma)$ with mean $\mu$ and covariance matrix $\Sigma$, what is the probability that $\forall j\in {1,\ldots,n}:x_1 \geq x_j$?

-
@gregor What is "l" in this problem? Is it fixed (but arbitrary), or something else? –  G. Jay Kerns Nov 3 '10 at 19:17
@gregor are you interested in some particular value for $\Sigma$ ? do you need to calculate a limit when the dimension is large ? do you need to simulate things? –  robin girard Nov 4 '10 at 12:15
@GJ Kerns: l is fixed but arbitrary, question updated –  gregor Nov 8 '10 at 14:53
@girard: I am most interested in an analytical approach. $\Sigma$ can be arbitrary. Dimension can be small. –  gregor Nov 8 '10 at 14:57
Without any loss of generality you can take l = 1. –  whuber Nov 8 '10 at 14:57

The question reads to me like the OP was asking when $U = (X,Y,Z)^{\mathrm{T}}$ are jointly normal then what is the probability $P(X \geq Y \mbox{ and } X \geq Z)$?

For that question we could look at the joint distribution of $AU$ where $A$ looks like $$A=\left[ \begin{array}{ccc} 1 & -1 & 0 \newline 1 & 0 & -1 \end{array}\right]$$ Of course, $AU$ is also jointly normal with mean $A\mu$ and variance-covariance $A\Sigma A^{\mathrm{T}}$, and the desired probability is $P(AU > \mathbf{0}_{n-1})$. We could get this in R with something like

set.seed(1)

Mu <- c(1,2,3)

library(MCMCpack)
S <- rwish(3, diag(3))  # get var-cov matrix

A <- matrix(c(1,-1,0, 1,0,-1), nrow = 2, byrow = TRUE)

newMu <- as.vector(A %*% Mu)
newS <- A %*% S %*% t(A)

library(mvtnorm)
pmvnorm(lower=c(0,0), mean = newMu, sigma = newS)


which is about 0.1446487 on my system. If a person knew something about the matrix $\Sigma$ then (s)he might even be able to write something down that looks like a formula (I haven't tried, though).

-
+1 Very nice! This problem had to require numerical integration (except for special cases such as all means being equal), so the availability of this package and the reduction of one in dimensionality are both useful contributions. By the way, as a check you can compute P(Y>X and Y>Z) = 0.3200386 and P(Z>X and Z>Y) = 0.5353126; the three results sum to 0.9999999, which is reasonably close to 1. –  whuber Nov 3 '10 at 18:28
@whuber Thanks. Thanks also for following through with P(Y>X and Y>Z) and P(Z>X and Z>Y); that didn't occur to me. –  G. Jay Kerns Nov 3 '10 at 19:14

Answer updated thanks to remarks from Whuber and Srikant

Proposition Let C=[C_1;C_2] be a 2*n matrix, $X^0=(X^0_i)\sim \mathcal{N} (0,\Sigma)$ $\mathbb{R}^n$ valued. Let $\Sigma^Y=^tC\Sigma C=(\sigma^Y_{ij})$. Then, for $u_1,u_2\in\mathbb{R}$

$P(^tC_1X^0\geq u_1\text{ and } ^tC_2X^0\geq u_2)=\mathbb{E}\left [ \bar{\Phi}\left (\frac{u_2-\frac{\sigma^Y_{21}}{\sigma^Y_{11}}^tC_1X^0}{\sqrt{\sigma^Y_{22}-\frac{\sigma^Y_{21}\sigma^Y_{12}}{\sigma^Y_{11}}}} \right )1_{ ^tC_1X^0\geq u_1 } \right ]$

where $\bar{\Phi}=P(\mathcal{N}(0,1)>z)$

Answer to the question when the dimension is 3

Assume $i=1$, $\Sigma=(\sigma_{ij})$. The probability $P(X_1>X_2 \text{ and }X_1>X_3)$ is obtained using the preceding proposition with $X^0=X-\mu$, $C_1=(1,-1,0)$, $C_2=(1,0,-1)$, $u_1=\mu_2-\mu1$ and $u_2=\mu_3-\mu1$. This gives

$\sigma^Y_{11}=\sigma_{11}+\sigma_{22}-2\sigma_{12}$

$\sigma^Y_{22}=\sigma_{11}+\sigma_{33}-2\sigma_{13}$

$\sigma^Y_{12}=\sigma_{11}+2\sigma_{23}-\sigma_{31}-\sigma_{21}$

Proof of the proposition

Assume $c\in\mathbb{R}^n$ and $\Sigma$ has full rank. It is easy to show that for any $u\in\mathbb{R}$ $$P(^tcX^0>u)=\bar{\Phi} \left (\frac{u}{\|\Sigma^{1/2}c\|_2} \right )$$

Let us denote $Y_1=^tC_1X^0,Y_2=^tC_2X^0$. From the correlation theorem, since $Y=(Y_1,Y_2)$ is centered gaussian in $\mathbb{R}^2$ with covariance $\Sigma^Y$ then $Y_2|Y_1$ is gaussian with mean $\frac{\sigma^Y_{21}}{\sigma^Y_{11}}Y_1$ and variance $\sigma^Y_{22}-\frac{\sigma^Y_{21}}{\sigma^Y_{11}}\sigma^Y_{12}$.

This, with $P(Y_1>u_1 \text{ and } Y_2>u_2)=\mathbb{E}\left [\mathbb{E}[1_{Y_2\geq u_2 }|Y_1] 1_{Y_1\geq u_1 }\right ]$ gives the desired result.

How to extend the proposition

If we want to be able to solve the initial problem with dimension larger than $3$, we need to compute $P(\forall j \; ^tc_jX^0\geq u_j)$ (for well chosen $u_j$). Set $Y=(Y_1,\dots,Y_n)$ with $Y_j=^tc_jX$ centered $\mathbb{R}$-valued gaussians.
You can use the correlation theorem iteratively to derive the distribution of $Y_1|Y_{2:n}$, $Y_2|Y_{3:n}$..... This may give something like a recurcive formulation of the solution to the proposition when C is $p*n$ (recurcive on $p$).

-
But, your answer gives the probability that $P(X_i >= X_j)$ for a specific value of $j$. It does not take into account the possibility that $X_i < X_k$ for some $k \ne j$. My intuition suggests that the answer is $\frac{1}{p}$ where $p$ is the dimension of the random vector. –  user28 Nov 2 '10 at 15:30
My intuition is flawed! It cannot be $\frac{1}{p}$. A simple simulation shows otherwise. –  user28 Nov 2 '10 at 15:52
@Srikant oups ... I have updated the answer... but I won't go any further than n=2 (the idea is here but there is too much calculation for me :) ) –  robin girard Nov 2 '10 at 16:08
This is a nice try but unfortunately Part 2 is incorrect (even after interpreting \Phi as the Gaussian probability in the upper tail): the right answer has to involve an integral of the Gaussian CDF, not the product of two of them (as the iterated expectation indicates). Alternatively, consider what happens when both variances are 1, the correlation coefficient approaches 1, and u1=u2: the joint probability that X1>u1 and X2>u2 should converge to Pr[X1>u1] (due to near-perfect correlation), but on the contrary the first factor in the right hand side goes to zero. –  whuber Nov 2 '10 at 18:06
@whuber I should not try to write anything else today, to many mistakes in a few hours ;) ... anyway I have updated the answer but it is not friendly anymore... maybe there is a way to make the calculation in the particular case of the question! –  robin girard Nov 2 '10 at 18:40

I interpreted the question to ask the distribution of the maximal element of a multivariate normal. In this case, the CDF can be computed from the CDF of a multivariate normal. This usually doesn't have a nice solution (even in terms of the univariate normal CDF), however can be evaluated numerically. In R:

library(mvtnorm)
# given xl, mu and sigma
pmvnorm(upper=rep(xl,length(mu)), mean=mu, sigma=sigma)


However on re-reading the question, it seems to be asking the probability that a particular element of the vector is maximal. In this case, I'd agree with G. Jay Kerns.

-
I think the question isn't fully specified and so it is hard to tell exactly what the OP meant without asking him directly. Maybe instead of drafting a solution to a hypothetical problem I should have asked for clarification. Why not do that now? :-) –  G. Jay Kerns Nov 3 '10 at 19:16