Wednesday, November 18, 2009

Wednesday Math, Vol. 97: The Birthday Problem

Let's say you have a classroom with 30 people. What is the probability that at least two people in that group share a birthday? On first glance, most people will think the answer is somewhere around 30/365, or about 1 chance in 12, an unlikely occurrence. The real probability is about 73% that there will be a birthday in common and only 27% that everyone will have a unique birthday. The probability of a birthday in common is a 50-50 proposition if the classroom has only 23 people.

Some books call this The Birthday Paradox, but that's an incorrect use of the word. In math, a paradox is a logical conundrum where false implies true and vice versa, the kind of thing Jim Kirk used to use to blow up computers. This is just a counterintuitive result, which is a different kettle of fish.

When I teach this material, I always start with "I will bet anyone a nickel that there are at least two people in the room that share a birthday." I ask if there are any takers. If there are, I say "Never bet with a math teacher in a situation like this. The probability will always be against you."

Figuring out the probability of "at least two people share a birthday" is tricky if you want to do it directly. It could be exactly two people with the same birthday, or it could be two pairs of people sharing two separate days or three people on the same day or any of many other combinations. The complementary event is "no one shares a birthday". This is a much more easily defined and computed. The technique is to find the probability of no one sharing, then subtract that number from 1 to get the probability of at least two sharing.

If the group has only one person, it is impossible to get two people to share a birthday. Any day of the 365 choices will work perfectly well. (I always ask if there was anyone born on February 29, just to be on the safe side. I don't think I've had anybody answer yes to that question yet.) If there are two people, then the second person can be born on any of 364 days that will not match the birthday of the first person. As we add people, each person added has a slightly lower chance of being unique and a slightly higher chance of matching one of the people already in the group. The probability of no matches in a group of k people is the fraction

365/365 * 364/365 * 363/365 * ... * (366 - k)/365

On a scientific calculator, there will be a choice in the Probability menu named nPr. The easier way to write this problem is

nPr(365, k)/365^k

(Note: different calculators write the nPr function in different ways. A TI-89 writes it with parentheses. Other Texas Instruments calculators will input this function as 365 nPr k.)

One of the challenges with probability is that though a probability is always going to be a number between 0 and 1, we often get a very large number being divided by an even larger number to get a probability and some calculators will give you an error when you input the formula. A TI-83 will balk at the formula when k = 40. Excel will stop giving an answer when k = 121. The mighty TI-89, on the other hand, will give an answer even when k = 365.

The easiest way to get around this overflow problem is to use the spreadsheet to create the fractions 365/365, 364/365, 363/365, etc. then multiply all these together. That way, neither the numerator or the denominator gets too big for program.

No comments: