The Birthday Problem
The well-known birthday problem:
How many people do you need to assemble before the probability that some two of them have the same birthday is greater than 0.5?
Assumptions: (1) A year has 365 days (no leap year), and (2) By “same birthday”, we only mean the same day and month (not necessarily the same year).
My first intuition was 183 — the smallest number that is more than half the number of days in a year. But as it turns out, 183 is the number of people you need to assemble before the probability that someone has the same birthday as you — a specific person — is greater than 0.5!
Look closely. The question is not about someone matching a particular person’s birthday. It is about the birthdays of some two people matching. Enough said. What is the right answer then, and why? How do we generalize this to matching the birthdays of some N people?
If you are guessing or have worked out a solution now, please leave comments.
The point of asking such questions (even though they might seem trivial to some) is to further our own understanding, and more importantly, to enjoy the process of understanding! So, if you already know the answer, please defer commenting.
Is it 21?
My method:
If you pick any pair of people, the probability that they have the same birthday is 1/365.
Lets say we need n people.
Since there are nC2 (that’s combinations of 2 picked from n persons) possible pairs, the probability that at least two of them will have the same birthday is nC2 * 1/365.
So we have:
n(n-1)/2 * 1/365 > 0.5
=> n > 20
sids
May 20, 2008 at 2:19 am
Well, I haven’t yet been able to come up with an approach for this problem. But I agree with yours. Seems intuitive.
(By the way, your approach works out to n = 20, not 21.)
Mandar
May 20, 2008 at 3:17 pm
There is something not right about this solution, although I can’t pinpoint that. I am saying this because the answer is 23 and not 20. And I know how to get to 23. Let me see if I can figure out what is the mistake in what Siddhartha has stated. I’ll try to get back.
sanket
May 20, 2008 at 7:28 pm
@sanket
Yeah. After I saw Siddhartha’s approach, I looked up a solution on the Web to verify his answer. His approach seemed very intuitive to me. It still does.
The solution I looked up on the Web approached the problem from the opposite direction — for an assembly of n people, what is the probability that some two of them do NOT have the same birthday?
Consider only two people first. The probability that they have the same birthday is 1/365.
So, for 2 people, we have probability (1 – 1/365) that the birthday of the second person does NOT match with that of the first. Let’s call this the first term.
For the 3rd person, we have probability (1 – 2/365) that the birthday of any of the two earlier people does NOT match with that of the third person –> second term
For the 4th person, we have probability (1 – 3/365) that the birthday of any of the three earlier people does NOT match with that of the third person –> third term
… and so on up to
For the nth person, we have probability (1 – (n-1)/365) that the birthday of any of the n earlier people does NOT match with that of the nth person –> (n-1)th term
Therefore, the probability that some two of the n people do NOT have the same birthday is given by
P = first term * second term * third term * … * (n-1)th term
We need (1-P) to be greater than 0.5.
Wrote a program for this and verified. At n = 23, it exceeds 0.5.
Is this the approach you followed too?
But still I find Siddhartha’s argument as intuitive as the one above. Am confused now.
Mandar
May 20, 2008 at 8:25 pm
>> Since there are nC2 (that’s combinations of 2 picked from n persons) possible pairs, the probability that at least two of them will have the same birthday is nC2 * 1/365
Umm.. I noticed a technicality that invalidates this — nC2 can get bigger than 365. Therefore, nC2 * 1/365 cannot be a probability at all. Hence, 20 cannot be the answer.
But I am unable to explain why that intuition is incorrect. Anyone have an idea about that?
Mandar
May 22, 2008 at 11:36 pm
If you think of each pair of people as a roll of a die with 365 sides, obviously you will never roll enough times to get P=1. If you have 365 people, P=1.
This contradiction occurs because the birthdays of the pairs of people are not independent events. They’re related. That is, if I’m in the group of people, I don’t get a new birthday each time I’m paired with someone to compare our birthdays.
One person has a birthday. P of having a pair of people with the same birthday (with only one person) is 0, since there are no pairs. P1 = 0.
The second person has a 1/365 chance of matching birthdays with the first person. P2 = 1/365.
The third person may not be needed for a birthday matching pair to be present. If needed, there is a 2/365 chance of a match. P3 = 1/365 + (364/365 * 2/365).
P1 = 0, For n>1
Pn = P(n-1) + (1-P(n-1) * (n-1)/365.
This should mean that P365 = 1, so P366 = 1 + (1-1 * (365/365)) = 1 + (0 * 1), and likewise for n > 365.
Charles
August 29, 2008 at 6:10 am
Look at it this way:
P(one person having a birthday): (365/365)
P( two people having different birthdays):(365/365)(364)(365)
P(3 people having diff bdays):(365/365)(364/365)(363/365)
etc…
P(23 diff bdays):(365/365)(364/365)…(343/365)=.4927…
This means that the prob of 23 people having different birthdays is 49.27%. OR that the probablility of there being at least one bday the same is 50.73%
Tony
September 20, 2008 at 6:33 pm