Monday, March 21, 2011

The Tim Hortons School of Probability

Do you know what this object is? We've just come to the end of that late-winter Canadian ritual when we line up to buy coffee, hoping for the magic words: "Win donut / Gagnez un beigne".

There are a couple of neat posts here and here, using "roll up the rim" to illustrate the binomial distribution. But you can also use it to illustrate the geometric distribution.

The geometric distribution (GD) gives a distribution on the number of trials before the next win. It's like the binomial distribution (BD) for impatient people: The BD asks, "If I buy 20 coffees, how many prizes can I get?" while the GD asks, "How many coffees do I have to buy until I get my next prize?"

More formally, let p represent the probability of receiving a winning cup, and let x represent the number of coffees you buy until you receive your next winning cup. Then since x follows the GD, we have
Rather than Pr(x), the probability of winning in exactly x cups, you're probably more interested in the probability of the next win happening in up to and including x cups. This is given by the cumulative distribution function F(x), where
Notice that Pr(x) forms a geometric series for x = 1, 2, ..., so using the geometric sum formula, we have

As we can see, the good news is that F(x) goes to 1 very quickly as x increases.  This year's contest had published odds of p = 1/6, so using F(x), we have F(5) = 0.598; F(10) = 0.839; F(20) = 0.974; and F(30) = 0.996. That is, if you buy a coffee a day, your chances of winning within a month are over 99%.

The bad news, sort of, is this: say you bought a coffee today, and lost. From the GD, how long do you now have to wait before your next win? Measuring time x from before you bought the first cup, we now know that x > 1, since the first cup is a loser.  Thus, we need to calculate the conditional probability Pr(x | x > 1).  This is given by
That's very tidy.  In general, you can show that Pr(x | x > m) = Pr(x - m) for any m > 0.

But now think of it this way: you already bought the losing cup, so how long do you have to wait after that until you win? Well, x is the time from before the first loss, so let y = x-1 be the time from after the first loss. Then from the above, Pr(y | x > 1) = Pr(y), the same as Pr(x). In other words, if you know you lost already, you still have the same waiting probabilities before your next win!

This seems perverse, but it actually makes sense: it's the memoryless property.  Tim Horton (rest his soul) is not watching you buy coffee, and adjusting the order of cups as you win or lose.  Instead, each play is independent and has the same odds.  For the same reason, if you take a coin and happen to flip a million tails in a row, your odds of getting a tail on the next flip are still 1/2; the coin doesn't remember.

Just something else to think about next time you see the dreaded "Please Play Again / Reessayez SVP".


Anonymous said...

What happened to the "And Now A Word From Our Sponsors" blog? Sorry to bother you, I'm just curious if someone complained to you or something. I thought it was insightful and you brought up good points.

Andrew said...

It will be back in a couple of months. I had to take it down temporarily for reasons I will explain when I re-post it.

Craig said...

Thanks for the link and the kind words, Prof. Eckford. Much appreciated -- keep up the great work!