The classic birthday problem goes like this: there are N students in a classroom. What’s the probability that at least 2 of them will share the same birthday? Consider that a year has 365 days, and that a person has an equal chance of being born on each day.

Let’s say N = 23 (you’ll see why this is the most used N on examples later on).

The easiest way to proceed is to reverse the problem. That is, let’s first calculate P’, the probability that in the group of 23 people no one share a birthday with anyone else. Then we will just need to do 1 – P’ to find P, the probability that at least two people share a birthday.

First imagine there’s only one person in the room. His probability of not sharing a birthday with anyone else is 1 (i.e., 100%, or 365/365).

Now add a second person. His probability of not sharing a birthday with the first person is 364/365 (his chance of having the same birthday is 1 in 365, so his chance of not having the same birthday is 364 in 365). For the third person it’s 363/365 and so on.

You need to multiply the individual probabilities together because we want the event of the first person not sharing a birthday AND the second person not sharing AND the third person AND so on.

So P' = (365/365)(364/365)(363/365)...(343/365) = 0.492703

So P = 1 - P' = 0.507297

You can derive a formula to calculate it right away.

P' = (365 * 364 * 363 ... * 365 - n + 1) / 365^n

P' = 365! / (365^n * (365-n)!)

Calculating The Other Way Around

Calculating P, the probability that at least two people share a birthday, straight away is more difficult. And that’s because you need to be careful not counting events twice.

For instance, you could imagine that to calculate P you could do like this:

1. Start with one people in the room. His probability of sharing a birthday with anyone else is 0.
2. Then add another person. His probability of sharing a birthday is 1/365.
3. Add a third person. His probability of sharing a birthday is 2/365.

So on and so forth. This reasoning is not correct though, and it would give you a probability of at least two people having the same birthday of 69.3%, when the correct value is 50.7%.

The probability using this approach is incorrect and larger because you are counting many events twice. For instance, if students 1 and 2 share a birthday the probability of student 3 share a birthday with anyone else would be 1/365, and not 2/365 as stated above.

The fix is simple: for each new person in the rool you need to find his probability of sharing a birthday with anyone else GIVEN that none of the people already in the room share a birthday (cause if they do you have already counted it).

So the calculation becomes:

1. Put the first person in the room. His probability of sharing a birthday with anyone is 0.
2. Put the second person in the room. His probability of sharing a birthday with anyone is 1/365.
3. Put the third person in the room. His probability of sharing a birthday with anyone, given that the previous people didn’t, is (1 – 1/365) * (2/265). Therefore (364/365)(2/365)
4. Put the fourth person in the room. His probability of sharing a birthday with anyone, given that none of the previous people did, is (1-P(3)) * (3/365).

So on and so forth.

So basically for the Nth person, the probability of him sharing a birthday with anyone in the room already, given that no one before did, P(N), is:

P(N) = (1 - P(N-1)) * ((N-1)/365)

And P(1) = 0.

If you want to calculate the probability with 23 people in the room, therefore, you just need to add all the individual P(N).

The Birthday Paradox

The paradox in this problem is related to the fact that with just 57 people in the room you’ll already achieve a probability of 99% that at least two people will share the same birthday. However, to achieve 100% you’ll obviously need 366 people, which is 1 more than the number of days in the year.

This principle has been used, for instance, to ellaborate cryptographic attacks.

Related Problems

You’ll observe this pattern on a wide range of probability problems. For instance, suppose that a lottery picks 6 numbers at random, and the range of the numbers available is 1 through 45.

What’s the probability that a certain number will be picked?

As with the birthday problem it’s much easier to invert the problem. What’s the probability that a certain number will NOT be picked?

P' = (44/45)(43/44)(42/43)(41/42)(40/41)(39/40)

P' = 44!39! / 45!38! = 39 / 45 = 0.866666666666.

So P = 0.13333333333.

You could go the other way around, but you need to remember to remove repeat events.

P = (1/45) + (44/45 * 1/44) + …

That is, the probability of the number appearing in the first pick is 1/45. In the second pick is 1/44 multiplied by the probability that the number didn’t appear in the first pick. In the third pick the probability is 1/43 multiplied by the probability it didn’t appear in the first two picks, and so on.