As living beings we rely heavily day to day on our intuition. And most of the time it does not let us down. However, sometimes our intuition fails us and we feel compelled to call that event a paradox. This is the case with the birthday problem.
I pose the following question. How many random people need to be gathered before we have a 50/50 chance that two of them will share the same birthday? The pigeon hole principle tells us (if we ignore leap year) that we need 366 people to guarantee two share the same birthday. Thus we might feel inclined to say that we need 183 people to have a 50/50 shot at two sharing a birthday. Not only is this wrong, it is way off the mark. To see this we discuss a few preliminaries and assumptions.
First, we will discuss assumptions. In this, as mentioned in the previous paragraph, we will be ignoring leap year birthdays. They do affect the result but not in a significant way, and the math is much easier if we ignore them. The next assumption we make is that nobody at the gathering knows each other. This assures that we have independent events.
For the preliminaries we will be dealing with probability. In particular, the probability of independent events and the probability of an event not occurring. Recall that if we have two independent events and then the probability of and occurring is the probability of times the probability of . That is . Next the probability of an event not occuring is . Okay without further ado let us explore this problem.
To start we will ask the question, given people in a room what is the probability that none of them will share a birthday. Let us begin with supposing that two people are in the room. Then we are asking what is the probability that they have different birthdays. Well person 1 can have any of the 365 possible birthdays. Then person 2 must have one of 364 birthdays. In brief we have . Remember that this is the probability that they do NOT share a birthday. If we introduce person 3 then our probability becomes
So we can write down the formula for people as follows . Now we can attempt to solve this for or we can pick a few test points and squeeze down to the right one. That is for the probabilities are . Aha! we see that between 20 and 25 we must achieve our desired . Already we see how wildly off the idea that we needed 183 people is. So let us proceed to find our value. For we get . Aha again! There we have it. We only need 23 people for approximately a 50% chance that no two share a birthday. This means that there is a 50% chance that two of them will share a birthday.
So let us explore this a little more. If 183 people gather as we initially thought was needed then the chance that none of them will share a birthday is approximately . That number is so small it is negligible! That means that it is almost guaranteed that in any gathering of 183 people two will share a birthday. So as we have seen in this exploration intuition can sometimes fail us in a big way. This just goes to show that every claim, no matter how seemingly trivial, deserves to be checked and proved. There are a few other cases of failed intuition that we will explore later.