Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Estimating the chances of something that hasn’t happened yet

johndcook.com

Post reply on HN
Print view View original

141–150 of 155 posts

Re: Estimating the chances of something that hasn’t happened yet

#141

Post by carlmr »

gweinberg wrote: post #75
whack wrote: post #59

In the example given, the author says that the odds of a given page having a typo is less than 3/20 . Sure, but if we don't want a range, but an exact number ? That sounds like a more interesting challenge to me. Formal statement: - You have observed N events, with 0 occurrences of X - Someone wants to make a bet with you about the likelihood of X happening - Once you've quoted a number, your counter-party then has t…

I don't think you can do this. You have a reasonably good upper bound of the probability, but you don't have any justification for putting any lower bound other than zero on the probability. In particular, if you're considering the probability of a catastrophic event, it's probably better to find some other rationale for estimating the probability than just saying 'it has never happened before'.

Exactly, the maximum likelihood estimator given your data is 0. You can just have a looser or stricter upper bound, depending on your requirements. However without a better model of your distribution and/or better priors (experience), you won't get a tighter estimate.

Re: Estimating the chances of something that hasn’t happened yet

#142

Post by jdmichal »

PeterisP wrote: post #94
jdmichal wrote: post #32

Earlier quoted context omitted.

Minor correction to your otherwise excellent final statement: "... or equivalently the total number of [ pages with ] typos in the 20,000 page book is between 0 and 300." We're not measuring the number of typos on a page, but only whether the page contains a typo or not. So we can't speak about the number of typos.

The math in that article is based on the assumption that typos are scarce, because that's the situation where it makes sense that you've seen 0 events. If that probability is close to zero, the probability of two typos per page is insignificantly small and can be discarded, and the expected number of typos in the book is approximately equal to the expected number of pages with typos. So in the context of these assump…

There's no reason to be imprecise and potentially sloppy over a two-word difference. Especially when the comment is being targeted to explain something to someone who did not have a solid grasp of the material, which is obviously necessary to make a leap such as yours.

And I won't even bother with the argument that presence of one typo on a page might actually increase the probability of another typo on the same page or nearby pages. The idea that this principle is based on uniform distribution is discussed enough in other threads.

Re: Estimating the chances of something that hasn’t happened yet

#143

Post by gugagore »

taneq wrote: post #103
cperciva wrote: post #28

This reminds me of a different "rule of 3": If you want to compare two things (e.g., "is my new code faster than my old code"), a very simple approach is to measure each three times. If the all three measurements of X are smaller than all three measurements of Y, you have X This works because the probability of the ordering XXXYYY happening by random chance is 1/(6 choose 3) = 1/20 = 5%. It's quite a weak approach --…

> If the all three measurements of X are smaller than all three measurements of Y, you have X On a multitasking system, you should use the fastest benchmark run (assuming you're running the same code on the same data in all cases, and if you're not then you're not really benchmarking). This will be the one that is least influenced by any other processing going on.

That's the case when you think the measurement noise is only positive. But are there kinds of noise that reduce your benchmark time?

On one hand, I believe a piece of code has a true benchmark time, but we only measure noisy versions that are skewed positive due to multitasking noise. On the other hand, it seems important to make benchmark measurements in the context of the whole system. If A beats B in the best case (unloaded system), but doesn't win in the average case (taking the context into account), then that's important information.

Re: Estimating the chances of something that hasn’t happened yet

#144

Post by YeGoblynQueenne »

PeterisP wrote: post #137
YeGoblynQueenne wrote: post #123

Earlier quoted context omitted.

You always have more data -background knowledge- unless you've only existed in those last 10 minutes. And if something has really never happened before, like my alien invasion example, what have we learned by applying the rule of three? Honestly- perform the experiment yourself. Wait for X time, then calculate 3/X. Do you now have an upper bound on the probability that an alien invasion will happen?

Yes, I do have a reasonable (95% confidence, as per article) upper bound on the probability - as I haven't noticed an alien invasion during my lifetime, it seems reasonable to conclude that noticeable alien invasions are very rare events and happen less frequently than once every decade. Possibly much less frequently, possibly many orders of magnitude less frequently, possibly never, but that's how upper bounds work.

An upper bound of "maybe, who knows" is not useful or informative enough to make a whole "rule" about it.

Re: Estimating the chances of something that hasn’t happened yet

#145

Post by fernly »

Clearly this is a bad estimating rule for some processes. The one that popped into my mind is the probability of earthquakes (guess where I live...). This would have the probability of an earthquake declining with each quake-free year that passes, where in fact the USGS would say the opposite.

Re: Estimating the chances of something that hasn’t happened yet

#146

Post by gugagore »

fernly wrote: post #145

Clearly this is a bad estimating rule for some processes. The one that popped into my mind is the probability of earthquakes (guess where I live...). This would have the probability of an earthquake declining with each quake-free year that passes, where in fact the USGS would say the opposite.

There's something that feels different about that. You're talking about the rate of some event occurring (like a Poisson process), and measuring how many occurrences are in an interval (a year). What are the 6 samples you are collecting? 6 years of numbers of earthquakes in a year?

Edit: sorry I thought you were replying to another comment.

Re: Estimating the chances of something that hasn’t happened yet

#147

Post by johntiger1 »

This post is of course talking about the difference between MLE and MAP estimation. Consider the converse case: you flip a coin once and observe it is heads. Do you then conclude that the probability of heads is 100%? No, because even though you have data supporting that claim, you also have a strong prior belief in what your probability of heads should roughly be. This is encoded in the beta distribution, as mentioned in the article

Re: Estimating the chances of something that hasn’t happened yet

#148

Post by skybrian »

gugagore wrote: post #143
taneq wrote: post #103

Earlier quoted context omitted.

> If the all three measurements of X are smaller than all three measurements of Y, you have X On a multitasking system, you should use the fastest benchmark run (assuming you're running the same code on the same data in all cases, and if you're not then you're not really benchmarking). This will be the one that is least influenced by any other processing going on.

That's the case when you think the measurement noise is only positive. But are there kinds of noise that reduce your benchmark time? On one hand, I believe a piece of code has a true benchmark time, but we only measure noisy versions that are skewed positive due to multitasking noise. On the other hand, it seems important to make benchmark measurements in the context of the whole system. If A beats B in the best case…

The way I think about it is that benchmarks include deterministic operations (that happen every time) and nondeterministic operations (that don't). And all of these numbers are positive, since there are few things in the world that take negative time.

By taking the minimum, we focus attention on the deterministic operations. This isn't likely to be realistic for production, but production won't look much like your benchmark hardware anyway.

When making code changes, deterministic operations are the part you have most influence over and have the most impact. Removing an unnecessary, deterministic operation will speed up every run, not just some of them.

Re: Estimating the chances of something that hasn’t happened yet

#149

Post by hinkley »

hinkley wrote: post #89
zawerf wrote: post #62

Earlier quoted context omitted.

Is this a good method to use while trying out a lot of ideas? Usually when I am optimizing code, most of the ideas don't work out and performance remains roughly the same (or so I think - I don't really know and want a better workflow here). But if you do this test repeatedly, even if the code had identical performance, you'll get a false positive 5% of the time. And depending on the spread of the timings you might n…

Statistics is a tricky beast. If 3 runs gives you a 95% chance that your change is an improvement, and you use this process on ten different improvements, there's a 40% chance that at least one of them is bogus.

Would love to see a refutation from a downvoter.

Re: Estimating the chances of something that hasn’t happened yet

#150

Post by repsilat »

mikekchar wrote: post #118
ced wrote: post #107

Earlier quoted context omitted.

Man, I wish I understood frequentist statistics to know if your reasoning makes sense. Bayesianly, if O = "the XXXYYY ordering", and F = "algo B is faster than algo" A, then P(F|O) = P(O|F) * P(F) / P(O) then... what? There isn't even a clear P(O|F) likelihood without making assumptions about the process' noise. If the measurement is very noisy compared to the gain, then XXXYYY is just dumb luck, and doesn't tell you…

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 like…

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

Post reply on HN