1
$\begingroup$

We initially have M drunk guys located on the x-axis at positions $\mu_1,...,\,u_M$. As they are all completely "wasted", they will just randomly walk around in this 1D space for a while. After a few minutes, we want to find out which guy is located the furthest to the right on the x-axis.

Let us assume that their final locations are given by a gaussian distribution $\mathcal{N}(\mu_j,\sigma_j)$, centered around their initial position $\mu_j$ with a standard deviation $\sigma_j$, where $j \in \{1,...,M\}$. What is the probability of the $i^{th}$ being furthest to the right at the end?

My solution: Do a very ugly multidimensional integral, which is not numerically solvable, but reducible to a single integral:

$p_i = \int_{-\infty}^{\infty} \frac{1}{\sigma_i\sqrt{2\pi}} e^{-\frac{(x_i-\mu_i)}{2\sigma_i^2}} dx_i \Big[ \prod_{k \in \{1,...,i-1,i+1,...,M\}} \int_{-\infty}^{x_i} \frac{1}{\sigma_k\sqrt{2\pi}} e^{-\frac{(x_k-\mu_k)}{2\sigma_k^2}} \Big]$

As this is really ugly, I am wondering if there is a more elegant way of solving this problem?

PS: for clarification. this integral simply calculates the probability of each value of $x_k$ being smaller than $x_i$. This is why all integrals (except of the $i^{th}$) stop at $x_i$.

$\endgroup$
2
  • $\begingroup$ You can make it look slightly more elegant by writing it as $$p_i = \int_{-\infty}^\infty f_i(x) \prod_{j \ne i} F_j(x)\; dx$$ where $f_i$ and $F_j$ are the pdf's and cdf's of these normal distributions, but I don't think you can get a better formula to compute. $\endgroup$ Mar 27, 2019 at 15:07
  • $\begingroup$ @RobertIsrael Yes, thank you. This is a simpler version of the integral, but still doesn't solve the problem :( $\endgroup$
    – Samuel
    Mar 27, 2019 at 15:11

1 Answer 1

2
$\begingroup$

As I understand, you are looking at the distribution of the argmax of a set of independent Gaussian. This is a difficult problem and no solution has be found yet.

Nevertheless, these related questions here can give you some partial answers with pointers to the relevant publications :

$\endgroup$
3
  • $\begingroup$ Thank you for pointing this out! With "no solution has been found yet" you probably mean that no solution without an integral has been found right? $\endgroup$
    – Samuel
    Mar 27, 2019 at 20:35
  • 1
    $\begingroup$ Yes, no solution except the expensive computation of the integral you mentionned. $\endgroup$
    – Florian
    Mar 27, 2019 at 20:38
  • $\begingroup$ Thank you! That is a very specific and precise answer, which saves me a lot of time :) $\endgroup$
    – Samuel
    Mar 28, 2019 at 7:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .