3 ms·

Here's one that I learned from HN years ago (https://news.ycombinator.com/item?id=18463449 https://news.ycombinator.com/item?id=18463449) Rule of three: If you

Here's one that I learned from HN years ago (https://news.ycombinator.com/item?id=18463449 https://news.ycombinator.com/item?id=18463449) Rule of three: If you want to compare two things (i.e if code A is faster then code B), then measure each three times. If all three As are faster then the Bs, then there is a ~95% probability that is true. Derivation: We are trying to find the probability of selecting three As, from the set (ABABAB). We don't care about the order of the As, so this is a combinations without repetition problem: 6 choose 3 = n! / ((n-r)! r!)) = 6! / (3! 3!) = 120 / 6 = 20 There is only one state where all three As are chosen, so the probability of getting it by random chance (our null hypothesis) is: 1 / 20 = 5%. Hence 95% confidence.

kevinwang 6y ago
Uh oh... I think you're interpreting the probability incorrectly. Shouldn't this be "if we assume that a and b take the same amount of time, then there's a 5% chance that we would see this result?". Can't actually speak to the probability that a is faster than b without some kind of assumed prior distribution for a and b
- saeranv 6y ago
  Yes, this is correct.
- contravariant 6y ago
  It should also be pointed out that the one thing you're ruling out is that they have the same distribution. In particular it only provides weak evidence that the mean, mode, median of A is any faster than B's. In the worst case A happens to be a lot slower than B, but with very low probability.
- bo1024 6y ago
  Yep. It gets at, what is the meaning of "faster?" Implicitly we are saying the average runtime of A is smaller than the average of B. But if for example, B always halts in 10 seconds, and A halts in 1 second 99.99% of the time but A runs for 10 years 0.01% of the time, then A is "slower" but you'd need 10,000 trials to notice.
dmurray 6y ago
This is neat but I think your derivation needs another step: a Bayesian prior that before this experiment, you thought the probability of A beating B was 50%.
lalaland1125 6y ago
Both the statistical reasoning and the math are wrong here. First, this isn't really "95% confidence" of anything. You are computing the probability of seeing your outcome in the case that A and B have the same distribution. This is very counterintuitive and I highly recommend people read up on a p-values to get an exact sense of what's going on. A low p-value simply tells you that it's unlikely that A and B have the exact same performance, it doesn't really tell you that A is faster than B in any specific manner (mean, median, mode, etc). Second, the math here is wrong. The p value is actually 0.10, not 0.05 as presented here as you should also take into account the possibility of your test returning 3 Bs. You then get p = 2 * 1 / 20 = 2 / 20 = 0.1. (The exact terminology here is whether the test is a two-tailed or one-tailed test an usually you want to use the two-tailed test unless you have some special prior knowledge).
- saeranv 6y ago
  I think the math here should be right, although perhaps the confusion here is because I wasn't clear about the role of the order: We're ordering the trials by speed, and computing the probability of getting an AAABBB ordering. The probability of ordering AAABBB by random chance is 1/20. That's why we don't care about getting BBB first, and why getting AAA first does tell you that A is faster then B. You can also click on the link in the OP and see other people explaining the logic of the rule. If there's an error with either my explanation or others, I'm interested in hearing it.
  - lalaland1125 6y ago
    The problem is that you are equally likely to get a BBBAAA ordering which would give you the same Type 1 error as AAABBB in the case where A and B have the same distribution. The main key to remember when deriving a p value is that you are computing the probability of seeing an outcome at least as extreme given the null hypothesis, not the probability of seeing your particular outcome.
    - saeranv 6y ago
      I see your point. But isn't that only true for two-tailed tests? This sort of ordering problem seems more suited to a one-tailed test. Let's say for example, we represent the bins of the probability distribution as the number of B's we can obtain (0, 1, 2, or 3). In this case I am defining the statistical significance of our test ordering (AAABBB) as anything less than or equal to 0.05 of our probability distribution - which corresponds to the 0 Bs bin. This corresponds to a one-sided confidence interval of 95%. What am I doing wrong?

kevinwang 6y ago

Uh oh... I think you're interpreting the probability incorrectly. Shouldn't this be "if we assume that a and b take the same amount of time, then there's a 5% chance that we would see this result?". Can't actually speak to the probability that a is faster than b without some kind of assumed prior distribution for a and b

saeranv 6y ago
Yes, this is correct.
contravariant 6y ago
It should also be pointed out that the one thing you're ruling out is that they have the same distribution. In particular it only provides weak evidence that the mean, mode, median of A is any faster than B's. In the worst case A happens to be a lot slower than B, but with very low probability.
bo1024 6y ago
Yep. It gets at, what is the meaning of "faster?" Implicitly we are saying the average runtime of A is smaller than the average of B. But if for example, B always halts in 10 seconds, and A halts in 1 second 99.99% of the time but A runs for 10 years 0.01% of the time, then A is "slower" but you'd need 10,000 trials to notice.

dmurray 6y ago

This is neat but I think your derivation needs another step: a Bayesian prior that before this experiment, you thought the probability of A beating B was 50%.

lalaland1125 6y ago

Both the statistical reasoning and the math are wrong here. First, this isn't really "95% confidence" of anything. You are computing the probability of seeing your outcome in the case that A and B have the same distribution. This is very counterintuitive and I highly recommend people read up on a p-values to get an exact sense of what's going on. A low p-value simply tells you that it's unlikely that A and B have the exact same performance, it doesn't really tell you that A is faster than B in any specific manner (mean, median, mode, etc). Second, the math here is wrong. The p value is actually 0.10, not 0.05 as presented here as you should also take into account the possibility of your test returning 3 Bs. You then get p = 2 * 1 / 20 = 2 / 20 = 0.1. (The exact terminology here is whether the test is a two-tailed or one-tailed test an usually you want to use the two-tailed test unless you have some special prior knowledge).

saeranv 6y ago
I think the math here should be right, although perhaps the confusion here is because I wasn't clear about the role of the order: We're ordering the trials by speed, and computing the probability of getting an AAABBB ordering. The probability of ordering AAABBB by random chance is 1/20. That's why we don't care about getting BBB first, and why getting AAA first does tell you that A is faster then B. You can also click on the link in the OP and see other people explaining the logic of the rule. If there's an error with either my explanation or others, I'm interested in hearing it.
- lalaland1125 6y ago
  The problem is that you are equally likely to get a BBBAAA ordering which would give you the same Type 1 error as AAABBB in the case where A and B have the same distribution. The main key to remember when deriving a p value is that you are computing the probability of seeing an outcome at least as extreme given the null hypothesis, not the probability of seeing your particular outcome.
  - saeranv 6y ago
    I see your point. But isn't that only true for two-tailed tests? This sort of ordering problem seems more suited to a one-tailed test. Let's say for example, we represent the bins of the probability distribution as the number of B's we can obtain (0, 1, 2, or 3). In this case I am defining the statistical significance of our test ordering (AAABBB) as anything less than or equal to 0.05 of our probability distribution - which corresponds to the 0 Bs bin. This corresponds to a one-sided confidence interval of 95%. What am I doing wrong?