# The Birthday Paradox explained

###
The Source

The pigeonhole principle simply states that if there are *n* items, put into *m* different spots, or pigeonholes; and n>m, then there is at least one pigeonhole with more than one item. This seems logical, yet it can lead to very counterintuitive conclusions. The birthday paradox is one of these.

###
The Birthday Paradox

The birthday paradox is an old problem commonly used to show how statistics can come up with surprising, and counterintuitive results. The paradox asks the question: "How many people are needed to have a 50% chance that a pair of them share a birthday. At first the obvious solution seems to be a large number, perhaps half of 365. Statistics, however, tells us the answer is 23 people. What just happened?

###
The Math

Finding the number of ways to assign birthdays to 23 people results in numbers so large they are near impossible to work with. The number of ways to assign the birthdays is 365^{23}, or something like 74 followed by 75 zeroes. The common way to actually solve this, then, is to work backwards: what's the probability of *no one* sharing a birthday. This makes the birthday paradox actually workable.

We could call the probability of two people sharing a birthday P(B), and the opposite probability 1–P(B). With only 2 people, the probability of them sharing a birthday easy. There are 365 pairs that work, where they share a birthday. There are 365^{2} ways to assign two people birthdays. So the opposite probability is 364/365, and the probability is 1/365.

For three people, there are 363 possible birthdays that are different than the other two. So the probability of different birthdays is 1*(1-1/365)*(1-2/365), or 364/365 * 363/365.

So the general rule for 1-P(n), or f(n) is $$ frac{365-(n-1)}{365}cdot f(n-1) $$.

This can be converted to $$ f(n) = frac{365!}{(365-n))!365^n} $$

Work that out for 30 people, and you get .29. A .29 chance of no two people sharing the same birthday, so 71% chance of a shared birthday!

The problem is our intuitions think about the probability of someone having the same birthday of a *certain* person. The birthday paradox solves for *any *two people.

In fact, by 50 people, the probability is greater than 97%!