Estimating the chances of something that hasn’t happened yet

Re:Estimating the chances of something that hasn’t happened yet by mikekchar on Friday November 16, 2018 @01:09AM (#18466822)

The OP is making some short cuts. 1/(6 choose 3) means that they start with the assumption that every possible ordering is equally likely. If that is the case, then the odds that XXXYYY pops out is 5%. What happens if we change our assumption? Let's assume that XXXYYY is more likely. This would imply that algo B is faster than algo A. If we assume that any of the other (or all of the other) combinations are more likely, then this reduces the odds that XXXYYY would pop out.

This means that either we had it right (algo B is faster than algo A), or the result we saw was at least as unlikely as we predicted. That's what it means to have a "confidence interval".

I'll leave the Bayesian version to someone else because I don't really trust myself to do it.

[ Parent | on HN ]

Re:Estimating the chances of something that hasn’t happened yet by repsilat on Friday November 16, 2018 @04:59PM (#18472318)

> they start with the assumption that every possible ordering is equally likely

If the times in each run are independent, this assumption is (for some distributions) the weakest form of "X is not faster than Y."

For a distribution where this is not the case: assume

- X always runs in 999 seconds, and

- Y runs in 1000 seconds in 99% of runs and in 0 seconds the other 1% of the time.

Then XXXYYY is a very likely ordering (~97% chance), though Y runs faster than X "on average". (Not in median or mode though.)

For a more concrete example: say you have two sorting algorithms, one that is a little slower most of the time, but worst case O(n log n), and another that is usually a bit faster but can be O(n^2) on pathological input.

[ Parent | on HN ]