We received the following email from a student wondering about the Birthday Problem, and presenting a few seemingly logical (but unfortunately flawed) algorithms for figuring out the probability of two people in a group having the same birthday:
Hi. I had a couple of questions regarding your birthday problem.
Some friends and I started discussing this problem earlier today (how we came upon the topic is unknown.. basically, i think we overheard people discussing something similar). The paradox of it is, there are several seemingly-proper ways to approach this problem..
One friend suggested that the answer was simply, nCr/365 (number of possible pairs, times 1/365)
My contention was, of course, that after the first pair fails to share a birthday, the second pair should be examined with 1/364 probatility, and so on.. My example was this:
Let's say myself, Ryan, and Nate, are standing in a room.
My birthday happens to be May 17. The probability of Ryan having that birthday is 1/365. The probability of Nate having that birthday is also 1/365. So, the probability of either Ryan or Nate having my birthday is 2/365.
Supposing that neither Ryan nor Nate has my birthday, the only possible pair left is the two of them. Now, we know that neither of them has the birthday of May 17th. As a result, there are 364 possible birthdays remaining. The probability of nate's birthday being the same as Ryan's, since neither is May 17th, is 1/364.
Thus, the probability of EITHER case A or case B being true should be prob(A) + prob(B); that is, 2/365 + 1/364 = .0082267
Now, we basically all agreed that this made perfect logical sense in the comprehensible example of three individuals (which, conveniently, yields three pairs). But when I returned home to do some digging online, and found a few web pages discussing the problem, I found different algorithms (and, more importantly, results) for this problem.
I'll yield that my roommates and I are most likely wrong, since we're much less studied in the field than those who've written the websites. But I've yet to find one that properly explains the numbers used, or properly dismisses such combanatorics+probability ideas as those used in my own example. Can you help?
Here is our response to this student's question, providing 3 different ways of solving the problem, and trying to show why the method we suggest is the simplest algorithm.
I believe I may be of some assistance to you in figuring out this problem and why your proposed solution to the Birthday Paradox is close, but not quite correct. This email is rather long, I should warn you, so you may want to go get some Mountain Dew to get you through it :) Here are 3 ways to solve the birthday problem. The first is the easy way, the second is the easier of the hard ways, and the third is the somewhat more difficult method, which should however shed some light on why your calculation didn't work.(1) The Easy Way:
You may already understand this, as it's the way that's usually used. In fact, in the first 20 responses to a Google search for the Birthday Problem, it was invariably done the exact same way. Here's a quick explanation: in probability, the set of all possible outcomes of a trial is equal to the number of ways of succeeding plus the number of ways of failing and is thus equal to 1 when you divide the number of ways of succeeding + the number of ways of failing by the total number of possible outcomes. So:
Total probability for an event = Sum of all possible outcomes of a trial divided by the total number of possible outcomes in the sample space, which equals 1, since the numerator and denominator are always equal
Now, sometimes it's difficult to directly calculate the probability of success--as in the birthday problem--so we can use a simple mathematical trick to figure the probability in a different way. In our case, success of our trial is defined as finding at least 2 matching birthdays in a group of n people. Failure is not finding any matching birthdays at all, in which case everyone in the group has a different birthday. This is actually quite convenient, as we will see later on in the problem, because there is only one case for failure, whereas the # of possible cases for success is rather daunting and makes the calculations prohibitively taxing and messy. More on that later :) For now, the reason we want to find the # of ways to fail is that we can subtract the probability of failure from one to get the probability of success:
Now, let's see how we can fail to find 2 people with the same birthday in a group of n people. Well, look at the first person. There are 365 birthdays that person could have in order to not match anyone in the group of 0 people we've already looked at so far. So with one person, we have 365/365 ways to fail. Now let's look at the second person. Since that person can't have the same birthday as the first person, 364 out of 365 choices of birthdays will fail to match the first person's b-day, so taken in light of the first person's choice of birthdays, we have 365/365 * 364/365 = 364/365. Now, look at the third person. That person has 363 ways to not choose either of the previous 2 people's birthdays. This gives us 365/365 * 364/365 * 363/365 = 364/365 * 363/365 ways to fail to find a pair in a group of 3. This continues until we reach n, and we have the following summation: For i from 1 to n, sum[(365-i+1)/365]. Now that we have the probability of failure, we can just subtract it from one, and we have our probability of success! That was incredibly easy compared to the following ways of trying to calculate the probability of success directly.
(2) The "Easy" Hard Way:
The easy way to solve this problem without using the probability of failure involves summing up all the ways that the event will occur, but there will be overlap when we do that with this problem, so we must also subtract off the ways in which we've overcounted the possible outcomes. To simplify the math, I'm going to use a "toy" (much simpler) example--distributing 3 objects among 4 possible bins (or, to keep consistent with our example, the probability of at least 2 people in a group of 3 being born in the same season--Winter, Spring, Summer, or Fall) Here's a simple way to do this:
Now let's count the number of ways of having 2 people with the same birthseason. Divide it up into 3 cases: A = B, B=C, and A=C. First, let's look at A=B: there are 4 seasons that A and B could share, and for each one there are 4 possibilities for C's birthseason.
There are 4x4 ways to have A=B. By the same logic, you also have 16 ways for B=C and for A=C. So that gives us 48 ways. Unfortunately, we've covercounted, so we must subtract off the overlap. In each of the three examples we counted all 4 ways that we can have not just 2, but all 3 people with the same birthseason (A=B=C). Since we only want to count this possibility once, we must subtract off the other 2 times we counted it. Therefore, we must subtract out both of the extra times we counted each of the 4 ways for all 3 to have the same birthseason. This gives us 2x4 ways that we overcounted. Now we have 48 - 8 ways, which is 40. There are 64 total ways that the birthmonths of the 3 could fall (4x4x4), so the probability is 40/64 = 5/8.
If you would like to get this probability directly without duplicating and having to subtract off the overlap, you could have narrowed the cases a bit as follows:
So we have 3x4=12 cases for each of the 3 duplicates, and only count the cases where the third birthseason is different from the first two (A=B!=C; A!=B=C; A=C!=B). Then we can add the case that A=B=C, which adds four to the total possibilities. Thus we have 3(3x4) + 4 = 40, so again the probability is 40/64 = 5/8.
This method didn't seem too bad, did it? Well, for 3 people, it isn't. Add a fourth to the equation, though, and you now have to consider :
In general, with n people in a group you'll have to look at all the ways exactly 2 people can have the same birthday, plus all the ways exactly 3 people can share a birthday, etc... up to all the ways n-1 people can have the same birthday, plus the way all n can have the same birthday.
As you can see, in problems with many cases for success but only one you have to worry about for failure (A!=B!=C!=D), it's a lot easier to calculate for failure and then get the probability of success from that!
(3) The *Hard* Way (Conditional Probability):
The reason your answer didn't work is that you were essentially trying to use a third method of calculating the birthdays: Conditional Probability. You see, you calculated the probability of two people having the same birthday correctly (case A), but then you essentially said "Given that neither Ryan nor Nate has my birthday, what's the probability that they share a birthday?" This is exactly the setup for a conditional probability problem. Conditional probability is applied when you're looking for the probability that an event occurs *given* that another event has occurred (or, as in our case, given that another event has not occurred). Conditional probability is a tricky thing, and it's not always immediately obvious when and why it should be used. You may even be wondering why it's not used in the easy way of calculating this problem, where you seemingly base the decision for the ith person's b-day on the i-1 preceeding people's b-days, since the ith person can't duplicate that person's birthday. In short, the reason these are different is that in the way you tried to do it, you changed the probability space. The probability space of a set S -- P(S) -- is the set of all possible outcomes, which was mentioned in the easy solution. You'll notice that in case B, you're actually changing the number of possible birthdays from which we can choose to 364. In the easy solution, on the other hand, we're saying that out of the 365 birthdays possible we're going to choose one of the birthdays that hasn't yet been taken. I will try to show you how to correctly calculate the probability using conditional probability and the toy example from the second solution, but it won't be pretty, especially in an all-text format :)
Case A: Ryan and/or Nate shares a birthseason with me.
We can just sum up the possible outcomes for this part.
These 3 sum up to 28/64
Case B: Neither Ryan nor Nate has my birthseason, but they share a birthseason
What we need to use is Baye's Theorem:
P(E|F) = [P(E intersect F)] / [P(F)]
This equation can be read: "The probability of event E given that event F has occurred equals the probability of E occurring intersected with the probability of F occurring, divided by the probability of F occurring." What this gives us is a way of calculating the probability of an event E (Ryan and Nate have the same birthseason) given that another event has occurred (neither has the same birthseason as me) without having to worry about changing the probability space, because it is guaranteed to stay the same *relative* to the original probability space. It's really hard to grasp why this is true, believe me. I didn't learn how this actually works until I got to a 300-level prob/stat course; before that, it was pretty much just given to us and we used it without really understanding why. So here's how the calculation goes now that we have a formula:
Let's calculate the parts of our formula so we can put them together:
P(E): probability that B and C share a birthseason (ignoring A's
P(E) = 4/16 = 1/4, because there are 16 different ways to choose birthseasons for B and C and 4 of them have B and C sharing a birthseason
P(F): probability that neither B nor C shares A's birthseason (ignoring the
relationship between B and C)
P(F) = (4x3x3)/(4x4x4) = 36/64, because there are 4 options for A's birthseason, and then 3 options for B's and 3 options for C's birthseason
P(E intersect F): probability that E & F occur (B and C have the same
birthseason which is different from A's birthseason)
P(E intersect F) = (4x3)/(4x3x3) = 12/36, because there are 4 options for A's birthseason and then there are 3 options for the birthseason that B and C share, since it's different from A's (that's the numerator). Also, since it's required that A cannot be the same as B or C, we get 4 options for A and only 3 options for each of B and C in our denominator (just like the numerator in P(F)...)
Ok, let's plug the numbers into our formula!
P(E|F) = [P(E intersect F)] / [P(F)]
P(E|F) = [12/36] / [36/64]
P(E|F) = 12/64
P(Case A) + P(Case B) = 28/64 + 12/64 = 40/64 = 5/8
Shockingly enough, it came out exactly the same. I only recommend using conditional probability if it's absolutely necessary, which in the case of the birthday paradox it isn't, so I would advise against it. In fact, as you may have noticed already, conditional probability doesn't really help us at all in this problem. In the case where we used conditional probability we could have easily counted A!=B=C without conditional probability and it would've looked exactly like the second way I showed you (the "easy" hard way). All in all, stick with the first way I explained--it'll keep you a lot saner :)
You'll notice that P(F) in case B was the exact probability of case A not happening. In case A we looked at the probability that one or both of B and C shared A's birthseason. In case B, we analyze the probability of still finding a pair, given that case A didn't occur, which makes sense since cases A and B must be distinct--only one or the other can be true, not both, and not neither, so in order for case B to have a possibility of being correct, case A must have been false. This method very quickly becomes unmanageable with more than 3 people. The simple method is by far the best way to go about solving this problem. You may want to sit down and work some of the calculations that I did in this email in order to understand why it all works out. It's a long explanation and some of it is tedious. I may not have explained it all very well, so feel free to email me back with any questions you have. I hope this helps you understand the Birthday Paradox and why the probability works out the way it does!
============== Michael McKelvey ===============
Office for Mathematics, Science, and Technology Education
University of Illinois, Champaign-Urbana
MSTE website: http://www.mste.uiuc.edu
========= firstname.lastname@example.org ==========