# Most likely order of independent normal random events

The problem I have is, given $n$ independent normal distributions describing the times that $n$ random events occur at, what is the most likely order that they will occur in?

This questions follows on somewhat from this question on calculating the probability of a given ordering of normal random variables, and is related to this question on the probability that one event occurs before all other events. In the case of the 2nd post, the answers all used Monte Carlo simulation to find the answer. Ideally I'd like to find an analytical method of finding the most likely order.

My initial thought was that you could simply order the events by their mean. However, a simple example shows that this is not the case. For 3 events, $A$, $B$, and $C$, with times $N(17.836,2.968^2)$, $N(18.067,4.638^2)$, and $N(18.209,2.982^2)$ respectively, the most likely order of events is $BAC$ with a probability of $19.7\%$. The order $ABC$ only has a probability of $13.9\%$.

Unfortunately, it is looking more likely to me now that an exhaustive search over all possible orders is required. Edit: As joriki has pointed out, branch and bound can be used to reduce the search space in most cases. However, that can still be quite slow (as the method for calculating the probability of an order is slow).

I doubt you'll get a solution in closed form for this, but in practice you can do a lot better than an exhaustive search over all possible orders. Build the orders one by one (e.g., start with just $AB$, then add $C$ in the three possible places, etc.) and abandon a branch once the probability for the part you've built is already lower than the probability for the maximum found so far. Most of the orders will typically be very unlikely, and you can detect this at an early stage before you've added more variables. You can order the search according to the means, so that promising candidates come first, in order to improve the pruning.
• Yeah, I have considered branch and bound, but looking for something faster if possible. I was originally planning on using something like Murty's ranking algorithm to find the $m$ most likely orders by making pairwise swaps. – Palms May 18 '16 at 7:21
For anyone interested in this problem, I ended up considering a restricted form of the problem where the variances of each event were equal. In this case I was able to prove that the most likely order is given by sorting the events by their mean values. Using that proof I was then able to develop a method based on Murty's ranking algorithm for finding the $n$-th most likely order. Details can be found in this paper.