You are hereThe Birthday Paradox Explained
Submitted by Bart on Sat, 20060211 10:15
I don't think the Birthday Paradox is that complicated to understand... First, let's get away from the math for a bit. What if there are 367 people (curse you, Feb 29) in a room? What then is the probability that two of them have the same birthday? Why, it's guaranteed that two do! The "pigeonhole principle" says that if you keep picking unique birthdays for folks in the room, you will run out of unique birthdays before you run out of folks. Now, let's do a tiny bit of math. Suppose there are 120 folks in the room and they all have unique birthdays. Then what are the odds that a 121st person with a randomly selected birthday has the same birthday as one of them? Well, about 1/3. 1/3 of the unique birthdays are taken, and the other 2/3s aren't. That's pretty good odds, still. But now think of it this way...imagine we start with 120 unique birthdays in the room, and add people #121..#130. Each of these folks has a roughly 1/3 chance of colliding with the original 120. So now you ask, "what are the odds that in 10 tries you don't roll 1 or 2 on a sixsided die?" In other words, what are the odds that you fail to achieve a 1/3 probability in 10 tries? The answer, it turns out, is 2/3 to the 10th power, which is a little less than 2%. If this is counterintuitive to you, get a die and try it. You'll likely get bored before you get through 10 rolls of just 3..6. So it seems clear that if 130 people were in the room, two would almost certainly have the same birthday, because even if the first 120 didn't contain such a pair, one of the next 10 would. Now, it should all be coming clear. Imagine that instead we'd started with 110 people in the room and worked up to 120. By exactly the same logic, the odds would be almost identical. So in a room with 120 people, it's still almost certain that two will have the same birthday. You see where this is going. Since with two people in the room, there's little chance they'll have the same birthday, the number of people for which the chance of a same birthday is 50% is going to be somewhere between 2 and 120 (already less than half), but by our math it looks way closer to 2 than 120. If you're mathematically sophisticated, you can now write down the right equation to get the number of people achieving a 50% chance. If not, you can look it up. Hopefully, this is clear. I think I didn't make any giant leaps. Let me know if I am wrong.
