How to lower bound the probability that one Gaussian exceeds many others

Question

I am interested in upper and lower bounding probability that one component of a multivariate Gaussian exceeds all others. For instance, say we have a multivariate Gaussian RV $X \sim N(\mu, \Sigma)$ where $X \in \mathbb{R}^d$. I am interested in the probability $$ \Pr\{ X_1 \gt X_j \text{ for all } j\ge 2 \}. $$

My understanding from Kenneth Train's book on discrete choice modeling (ch. 5, equation 5.1) is that this computation is intractable when the number of variables in the multivariate Gaussian distribution is greater than 2.

However, it's easy to upper bound this probability as $$ \Pr\bigl\{ X_1 \gt X_j \text{ for all } j\ge 2 \bigr\} ~\le~ \min\bigl\{\, \Pr(X_1 \gt X_2),\, \Pr(X_1 \gt X_2), \,\ldots, \, \Pr(X_1 \gt X_d) \,\bigr\} $$ where the probability of each of the Gaussian two-way comparisons on the right hand side is easy to compute (see here for example). The bound is due to the fact that the intersection of all the constituent events must have a probability no bigger than each of them individually.

However, I haven't been able to come up with a useful lower bound for the same and am hoping someone here may have some useful suggestions on how to go about finding one.

Answer 1

$\newcommand{\R}{\mathbb R}\newcommand{\Si}{\Sigma}$We have to bound
\begin{equation*} p:=P(X_1>\max_{j=2}^d X_j) \end{equation*} from below.

Note that
\begin{equation*} p=(2\pi)^{-d/2}|\Si|^{-1/2} \int_{\R^d}dx\,1(x_1>\max_{j=2}^d x_j)\exp(-(x-\mu)^\top\Si^{-1}(x-\mu)/2), \end{equation*} where $|\Si|$ is the determinant of $\Si$, and \begin{equation*} (x-\mu)^\top\Si^{-1}(x-\mu)\le\|\Si^{-1}\|\,|x-\mu|^2 \\ \le\|\Si^{-1}\|(|x|+|\mu|)^2 \le\|\Si^{-1}\| \Big(\frac{|x|^2}{1-t}+\frac{|\mu|^2}t\Big) \tag{10}\label{10} \end{equation*} for any $t\in(0,1)$, where $\|\Si^{-1}\|$ is the spectral norm of $\Si^{-1}$ and $|\cdot|$ is the Euclidean norm of vectors in $\R^d$; to verify the last inequality in \eqref{10}, minimize the latter expression there wrt $t\in(0,1)$. So, \begin{equation*} p\ge |\Si|^{-1/2}\exp\Big(-\frac{\|\Si^{-1}\|\,|\mu|^2}{2t}\Big) \Big(\frac{\|\Si^{-1}\|}{1-t}\Big)^{-d/2}q, \end{equation*} where \begin{equation*} q:=P(Z_1>\max_{j=2}^d Z_j), \end{equation*} $(Z_1,\dots,Z_d)\sim N\Big(0,\dfrac{1-t}{\|\Si^{-1}\|}\,I_d\Big)$, and $I_d$ is the $d\times d$ identity matrix, so that, by symmetry, $q=1/d$.

Thus, \begin{equation*} p\ge L_t:= \frac1{|\Si|^{1/2} \exp\Big(\dfrac{\|\Si^{-1}\|\,|\mu|^2}{2t}\Big) \Big(\dfrac{\|\Si^{-1}\|}{1-t}\Big)^{d/2}\,d}. \end{equation*}

---

In particular, if $\mu=0$ and $\Si=s^2I_d$ for some real $s>0$, then, letting $t\downarrow0$, we have $L_t\to 1/d=P(X_1>\max_{j=2}^d X_j)=p$, so that the lower bound $L_t$ on $p$ is sharp in this case.