Some Comments on Several Versions of the Birthday Problem

 

Some Comments on Several Versions of the Birthday Problem

"Happy Birthday to Me!!! ... ok, it's coming up on my birthday and I was thinking about that old birthday problem. You've probably seen it. How many people must be in a room before the probability of at least two sharing a birth date (just month and year) is greater than 1/2?. Yeah, that one.
It is one of those problems that is best attacked by answering a different question, (there seem to be a lot of those in probability) what is the probability that NO two have a common birth date. If you begin by thinking of people entering a room one at a time, and calculate the probability that no two have a common birth date, then the probability after the n^th person enters is given by P(n)=P(n-1)*^(366-n) /₃₆₅. We are assuming a 365 day year here.. so P(1) = 1 (if you are the only one in the room, there is no match)..
Now the next guy has 364/365 probability of preserving the NO MATCH and so on for each new body.  So after three people the probability of no matches yet is \( \fract{365*364*363}{365^3}|).  After each calculation, we check to see if the probability of NO MATCH is less than 1/2, in which case the proabability of a match would be more than 1/2. It turns out that at n=23 the probability of at least one match is slightly over 1/2, about .507.
Actually, it only seems like the problem has been around forever. I saw a quote that it was created in 1932 by Richard von Mises, the Austrian born scientist whose work spans several areas of engineering science, however, the earliest citation I can find is " Mises, R. von. "Über Aufteilungs--und Besetzungs-Wahrscheinlichkeiten." Revue de la Faculté des Sciences de l'Université d'Istanbul, N. S. 4, 145-163, 1939.", so you decide which is right.
After you play with that for a little while, you might want to tackle one of several different variations, that can take it well beyond a high school classroom exercise. For example, the classical problem ask for when there is at least one match, but if you ask for the number so that the probability is 1/2 of exactly one matched pair, it gets a little tougher (OK, a lot tougher). With modern technology, it can be examined by students without some of the formal probability training if they are good at simulations. I gave this problem to one class and asked them to describe a way to simulate the event using a graphing calculator. The best answer I got was this one: a) Put n (for example 23) random integers from 1 to 365 in a list 1. b) sort the list in ascending order c) copy this list 2 and then replace the last number with zero and resort just this list (effectivly this moves the zero to the top and each number down one in the list from its natural position). d) Now do a logical L1=L2 store L3. This produces a list of ones when the n th term in the list is equal to the n+1 st term, ie, for each match. Sum this list to get the number of matches. e) repeat like crazy.
I thought it was a great way to solve it, although if you have Fathom or other good statistical software for simulations, it can be done much easier, but sometimes the software hides some of the understanding in the early stages of learning simulations. When I tried it (with Fathom) and using 23 for the sample size, and 5000 trials of the experiment, there were no matches in 2431 or 48.6% of them, there was exactly one match in 1829 or 36.6% of them, and to my surprise, there were 604 or 12% that had either two separate matches, or three of a kind.... and if you do the arithmetic, that leaves another 136 or almost 3% that had multiple matches beyond these (I used the unique value function of the program so I only knew there were less than 21 unique numbers in those cases). With the student method, adjacent ones on the third list would identify triplets etc, while seperated ones would indicate multiple pairs.
A couple of examples you might want to explore, and I will try to get back to solutions if they are not submitted sooner:
1) What happens to the birthday problem if you switch to a different number of days in the year (say 400 or 1000) or what if we use weeks or months... in short, is there a general formula for the number of people to reach the p=1/2 that there is at least one match.

2) what is the number of people needed to make the probability that EVERYONE has a match equal to or greater than 1/2?

3) and what if we only wanted to have two people who came close. What is the number of people that must be present to make the probability that at least two have birthdays no more than one day apart?

4) and finally, back to the original problem, suppose a group (several hundred) are entering an auditorium, and you know that the first person to enter having a birthday that matches someone already inside will win a prize. Ok, you know not to go first, and if you go too late, it will already be gone.... so where in the line do you insert yourself to have the highest probability of being the first to enter and have a birthday match in the room?
More on all of these later..good luck, and have fun..