2
$\begingroup$

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).

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Palms May 18 '16 at 7:21
  • 2
    $\begingroup$ @Palms: Then why did you write that it's looking likely that exhaustive search is required? It's always a good idea to write down your own thoughts in the question, to avoid people spending time telling you what you already know. $\endgroup$ – joriki May 18 '16 at 7:24
  • $\begingroup$ Well, branch and bound is an exhaustive search in the worst case. I'll edit the question to make it clearer. $\endgroup$ – Palms May 18 '16 at 7:28
  • $\begingroup$ @Palms: In the present case, the worst case seems highly unlikely. I wouldn't be surprised if one could even prove that when ordering the search according to the means a certain high proportion of cases is necessarily pruned. $\endgroup$ – joriki May 18 '16 at 8:03
  • $\begingroup$ Thanks for the input joriki. In most cases, ordering by the means is sufficient to find the most likely order. However, it's the cases like the one in the question that are difficult and unfortunately require examination of (as far as I can tell) all of the possible orders. $\endgroup$ – Palms May 19 '16 at 5:08
0
$\begingroup$

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.

This approach can probably be used reasonably well in cases where the variances are not too different from one another, but obviously there are no guarantees on getting the correct answer.

$\endgroup$

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.