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$ – Robert Israel Mar 27 '19 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 '19 at 15:11
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 '19 at 20:35
  • 1
    $\begingroup$ Yes, no solution except the expensive computation of the integral you mentionned. $\endgroup$ – Florian Mar 27 '19 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 '19 at 7:41

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.