4
$\begingroup$

Let $X = \left( {{X_1},...,{X_n}} \right) \sim \mathcal{N}\left( {{\mathbf{\mu }},{\mathbf{\Sigma }}} \right)$ be a Gaussian random vector and $I = \mathop {\arg \max }\limits_{i = 1,n} {X_i}$.

$I$ has probability mass function

$\mathbb{P}\left( {I = i} \right) = \mathbb{P}\left( {{X_i} = \mathop {\max {X_j}}\limits_{j = 1,n} } \right) = \mathbb{P}\left( {{X_i} - \mathop {\max {X_j}}\limits_{j \ne i} > 0} \right)$

and mathematical expectation

$\mathbb{E}I = \sum\limits_{i = 1}^n {i\mathbb{P}\left( {I = i} \right)} $

Generally speaking, for large $n$ and arbitrary covariance matrix ${\mathbf{\Sigma }}$ , computing $\mathbb{E}I$ is very difficult because it requires the numerical evaluation of high-dimensional normal orthant integrals. So, apart from the IID and INID cases with a diagonal covariance matrix ${\mathbf{\Sigma }}$, banded covariance matrices and degenerate cases such as ${\mu _j} \gg {\mu _{i \ne j}}$ , under which conditions on ${\mathbf{\Sigma }}$ (e.g. correlation decay) can we get simple, easy-to-evaluate numerical approximations to $\mathbb{E}I$ (and $\mathbb{V}I$ as well)?

The covariance matrices ${\mathbf{\Sigma }}$ I'm interested in look like this:

Covariance matrix

Until now, I’ve not been able to find anything about this problem.

Related question: Maximal component of a multivariate Gaussian distribution

$\endgroup$
1
$\begingroup$

The integrals one needs to evaluate are of the form $${\mathbb P}(I=1)=\int_{-\infty}^\infty dx\int_{-\infty}^x dX_2\int_{-\infty}^x dX_3\cdots \int_{-\infty}^x dX_n \,P(x,X_2,X_3,\ldots X_n)$$ and similarly for $I=2,3,\ldots n$. An efficient method to evaluate these integrals numerically for large $n$ has been developed in Estimating orthant probabilities of high dimensional Gaussian vectors with an application to set estimation (2016). The method has been tested for $n$ as large as $10^4$.

$\endgroup$
  • $\begingroup$ Thanks for the reference. I know the literature about normal orthant probabilities quite well, including this paper. Impressive progress has been made since the classical methods of Genz or Miwa. However, in my problem $n = \prod\limits_{k = 1}^d {{n_k}} $, where the ${{n_k}}$ are positive integers and $d$ is the problem dimension. In practice, $d$ can be up to, say, 30, so that $n$ can be very large (typically ${n_k} \sim 100$). That's why I'm rather looking for analytic approximation formulae for $\mathbb{E}I$ in special cases... $\endgroup$ – Fabrice Pautot Jul 23 '18 at 9:52
  • $\begingroup$ One interesting reference: adaptiveagents.org/argmaxprior#paper $\endgroup$ – Fabrice Pautot Jul 23 '18 at 10:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.