Built on Facts

This Sunday I was at an event that involved a number of drawings for door prizes. There were perhaps 30 couples there - it was, not to beat around the bush, a wedding registry shindig at Bed, Bath, & Beyond. (Did I mention I'm recently engaged? I am. It's the main reason for the endemic light posting, as I'm afraid the wedding bumps the blog down the priority list a bit. ;) )

There was something in the vicinity of 8 or so drawings from separate bowls, and each couple's number was placed in each bowl. The rules were such that a couple could only win once. One number was pulled twice, and that particular prize had to be re-drawn. My friend Michael and his fiancee Christine were there, and I turned to him and said "Hey, this is the Birthday Problem!" He immediately agreed, and our very patient fiancees gave each other their patented "Oh geez, they're about to launch into some tremendously nerdy discussion again" looks. Not that they mind, but of course the middle of a wedding registration is not an opportune time. But this blog is an opportune time!

The birthday problem is a famous exercise in the theory of probability, to show students (and remind professionals) that probability can behave in very counterintuitive ways. It goes like this. Let's say you have a room containing N randomly chosen people. What's the probability that at least two people share a birthday? Or more concretely, how big does N need to be before there's an even chance of at least two people sharing a birthday?

Well, let's start counting it out. If N = 1, the probability is zero because there's no one to share a birthday with. If N = 2, the first person will have some particular birthday, and the second person has a 1/365 chance of having the same birthday. Therefore the probability of sharing a birthday is 1/365 (we'll ignore leap years, which affect the numbers only slightly). If N = 3, things are more complicated because there's more possibilities. They might all have different birthdays, two might share a birthday, or all three might have the same birthday. For higher N these possibilities will grow enormously and make our calculation very difficult. So we take a shortcut. We'll only look at the probability that everyone has different birthdays. All the other cases fall into the "at least one duplication" category, so we don't have to separately worry about all the cases of multiple duplications.

So for N = 3, the first person has a birthday, the second person has a (364/365) probability of not sharing the birthday, and the third person has a (364/365)*(363/365) chance of sharing neither of those birthdays. So on and so forth for higher N. The probability of at least one duplication is just 1 minus the probability of no duplications. and our Sunday Function is just the resulting expression:

If you're not familiar with that notation, it just means write down the expression in parentheses with n = 1. Then write in down again for n = 2. Then for n = 3 and so on until you get to n = N. Multiply all those together and you have the result. It's just a compact way or writing the previous paragraph mathematically.

So for a group of N people, the probability of at least one duplication of birthdays is given by that Sunday Function. Let's graph it:

The probability turns out to be better than 50:50 for N as low as 23. Get a group of 41 together and there's a better than 90% chance two will share a birthday. Most people intuitively suspect the groups would have to be much larger, but usually this is because they're really thinking of the probability of two people having a specific pre-chosen birthday. The probability of two people sharing a birthday, whatever it happens to be, grows pretty quickly.

This generalizes to the door prize situation pretty easily. Instead of two people sharing the same birthday, we're looking at two drawings sharing the same pulled number. So replace 365 by the number of couples and repeat the calculation. Running the numbers for 30 couples and 8 drawings gives a 64% probability of at least one duplication. It's thus not exactly a surprise that one prize had to be re-drawn.

I'm happy to report that one of the numbers drawn was ours. We're now the proud owners of a $100 gift certificate to Sherwin-Williams. So if we ever need paint, I guess we're set!