The Birthday Paradox
The Birthday Paradox
What is the Birthday Paradox?
How many people do you need to have in a room before the probability that at least two people share the same birthday reaches 50%? Your first thought might be that as there are 365 days in a year, you need at least half that many people in the room, so maybe you need 183 people. That seems like a sensible guess and many people would be convinced by that.
However the surprising answer is that you only need to have 23 people in the room. With 23 people in the room, there is a 50.7% chance that at least two of those people share a birthday. Don't believe me? Read on to find out why.
This article in video form on the DoingMaths YouTube channel
Something to consider
Probability is one of those areas of mathematics that can seem quite easy and intuitive. However, when we try and use intuition and gut feeling for problems involving probability, we can often be a long way off the mark.
One of the things that makes the Birthday paradox solution so surprising is what people think of when they are told two people share a birthday. The initial thought for most people is how many people need to be in the room before there is a 50% chance of somebody sharing their own birthday. In this case the answer is 183 people (just over half as many people as there are days in the year).
However, the Birthday paradox doesn't state which people need to share a birthday, it just states that we need any two people. This vastly increases the number of combinations of people available which gives us our surprising answer.
Now we've had a bit of an overview, let's look at the mathematics behind the answer.
In this hub, I have assumed that every year has exactly 365 days. The inclusion of leap years would lower the given probabilities slightly.
Two people in the room
Let's start off simply by thinking about what happens when there are just two people in the room.
The easiest way to find the probabilities that we need in this problem will be to start off by finding the probability that the people all have different birthdays.
In this example the first person could have a birthday on any of the 365 days of the year, and in order to be different, the second person must have their birthday on any of the other 364 days of the year.
Therefore Prob(no shared birthday) = 365/365 x 364/365 = 99.73%
Either there is a shared birthday or there isn't, so together, the probabilities of these two events must add up to 100% and so:
Prob(shared birthday) = 100%  99.73% = 0.27%
(Of course we could have calculated this answer by saying the probability of the second person having the same birthday is 1/365 = 0.27%, but we need the first method in order to calculate for higher numbers of people later).
Three people in the room
What about if there are now three people in the room? We are going to use the same method as above. In order to have different birthdays, the first person can have a birthday on any day, the second person must have their birthday on one of the remaining 364 days and the third person must have their birthday on one of the 363 days not used by either of the first two. This gives:
Prob(no shared birthday) = 365/365 x 364/365 x 363/365 = 99.18%
As before, we take this away from 100% giving:
Prob(at least one shared birthday) = 0.82%.
So with three people in the room the probability of a shared birthday is still smaller than 1%.
Four people in a room
Carrying on with the same method, when there are four people in the room:
Prob(no shared birthday) = 365/365 x 364/365 x 363/365 x 362/365 = 98.64%
Prob(at least one shared birthday) = 100%  98.64% = 1.36%.
This is still a long way off the 50% that we are looking for, but we can see that the probability of a shared birthday is definitely rising as we would expect.
Ten people in a room
As we are a long way from reaching 50% yet, let's jump a few numbers and calculate the probability of a shared birthday when there are 10 people in a room. The method is exactly the same, only there are more fractions now to represent more people. (By the time we get to the tenth person, their birthday cannot be on any of the nine birthdays owned by the other people, so their birthday can be on any of the remaining 356 days of the year).
Prob(no shared birthday) = 365/365 x 364/365 x 363/365 x ... x 356/365 = 88.31%
As before, we take this away from 100% giving:
Prob(at least one shared birthday) = 11.69%.
So if there are ten people in a room, there is a slightly better than 11% chance that at least two of them will share a birthday.
The formula
The formula we have been using so far is a reasonably simple to follow one, and fairly easy to see how it works. Unfortunately, it is quite long and by the time we get to 100 people in the room, we will be multiplying 100 fractions together, which will take a long time. We are now going to look at how we can make the formula a little simpler and quicker to use.
Creating a formula for the nth term
Explanation
Look at the working above.
The first line is equivalent to 365/365 x 364/365 x 363/365 x ... x (365  n + 1)/365
The reason we end at 365  n + 1 can be seen in our previous examples. The second person has 364 days left (365  2 + 1), the third person has 363 days left (365  3 + 1) and so on.
The second line is a little trickier. The exclamation mark is called factorial and means all of the whole numbers from that number downwards multiplied together, so 365! = 365 x 364 x 363 x ... x 2 x 1. our multiplication on the top of the first fraction stops at 365  n +1, and so to cancel out all of the numbers lower than this from our factorial, we put them on the bottom ((365  n)! = (365  n) x (365  n  1) x ... x 2 x 1).
The explanation for the next line is beyond the scope of this hub, but we get a formula of:
Prob(no shared birthdays) = (n! x ^{365}C_{n}) ÷ 365^{n}
where ^{365}C_{n} = 365 choose n (a mathematical representation of the number of combinations of size n in a group of 365. This can be found on any good scientific calculator).
To find the probability of at least one shared birthday we then take this away from 1 (and multiply be 100 to change into percentage form).
Probabilities for different sized groups
Number of people
 Prob(shared birthday)


20
 41.1%

23
 50.7%

30
 70.6%

50
 97.0%

70
 99.9%

75
 99.97%

100
 99.999 97%

Using the formula, I have calculated the probability of at least one shared birthday for groups of different sizes. You can see from the table, that when there are 23 people in the room, the probability of at least one shared birthday is over 50%. We only need 70 people in the room for a probability of 99.9% and by the time there are 100 people in the room, there is an incredible 99.999 97% chance that at least two people will share a birthday.
Of course, you cannot be certain that there will be a shared birthday until you have at least 365 people in the room.
Questions & Answers
Comments
No comments yet.