Warning: Missing argument 2 for ted_filter_oembed_amp_iframe() in /home/kawalski/public_html/torontotutorteam.ca/wp-content/plugins/jetpack/modules/shortcodes/ted.php on line 108
The Birthday Problem can basically be stated as: in a group on n randomly chosen people, what is the chance that some pair will have the same birthday?
Just for some context, in a random group of 23 people there is a 50% probability that two people will have the same birthday. In a group of 70 people there is a 99% probability!
Solving the Birthday Problem
Let Pn represent the probability that some pair will have the same birthday in a group of “n” random people
We know that there are 365 days in a year, so there are 365 possible birthdays (ignoring leap years). Given this, the chance that any 2 people have the same birthday is 1/365
This means that P2 = 1/365, the probability of 2 people having the same birthday in a group of 2 people
The solution space for this problem can be divided into 2 distinct possibilities, either a pair of matching birthdays exists, or there are no matching birthdays. Given this we can say:
P(birthday match exists) + P(no birthday matches) = 1
P(birthday match exists) = 1 – P(no birthday matches)
Pn = 1 – P(no birthday matches amongst n people)
We established that P2 = 1/365
Put another way, if you have two people, there are 364 possible days where they do not match
P(no birthday matches, n=2) = 364/365
So P2 = 1 – 364/365
Now if we add in a third person, there are 363 possibilities that the third person’s birthday does not match with the first 2.
So the probability that the third person does not match with either of the first 2 is 363/365
In order for there to be no matches between all 3 people, the first 2 must not match, AND the third person must not match with the first 2. In probability, if A and B must happen, we take the product of their probabilities, so:
P(no birthday matches, n=3) = 364/365 * 363/365
Which means: P3 = 1 – 364/365 * 363/365
Following the same logic, if we introduce a 4th person who does not match with the first 3
P4 = 1 – 364/365 * 363/365 * 362/365
Following this trend:
Pn = 1 – 365-1/365 * 365-2/365 * 365-3/365 … * 365-n+1/365
The reason it is -n+1 (instead of -n) is because we begin comparing when there are 2 people, meaning if there are 2 people then there is 1 potential day they could match. The number of days that could match is always one less than the number of people there are.
Before we can continue with the birthday problem we need to quickly cover factorials. Factorials are denoted by an exclamation mark, and is the product of all of the integers up to and including any integer.
n! = 1 x 2 x 3 x … x n
Our goal now is to express Pn in terms of factorials.
Consider 365!/(365-n)! = 1*2*…*(365-n)*(365-n+1)*…*(365-1)*365/1*2*…*(365-n)
Notice how the numerator has all the same terms as the denominator, and more,
So we can cancel these out:
And we are left with 365!/(365-n)! = (365 – n + 1) * (365 – n + 2) * … * (365 – 2) * (365 – 1) * 365
And if we just change the order of the terms: 365!/(365-n)! = (365 – 1) * (365 – 2) * … * (365 – n + 2) * (365 – n + 1) * 365
Remember that Pn = 1 – 365-1/365 * 365-2/365 * 365-3/365 … * 365-n+1/365
And we can see that the numerators of Pn are practically the same as 365!/(365-n)! except for the bold 365 at the end.
Now if we look at the denominator of the product in Pn, it’s simply 365 multiplied by itself n-1 times, so 365n-1. But remember we have an extra 365 in the numerator, so if we multiply the denominator by an extra 365 we can cancel it out. So we will use a denominator of 365n
Putting it All Together
The final step is to combine all the pieces we’ve put together:
Pn = 1 – 365!/(365-n)! * 365n
By taking the factorial terms and dividing it by 365n we have recreated the long string of products in the original Pn formula, and this is the general solution to the birthday problem!
So if we return to the example of 23 people, all we do if plug in 23
P23 = 1 – 365!/(365-23)! * 36523 = 1 – 365!/342! * 36523 = 1 – 0.493 = 0.507
In a group of 70 people
P70 = 1 – 365!/(365-70)! * 36570 = 1 – 365!/295! * 36570 = 1 – 0.00084 = 0.99916
That’s the solution to the birthday problem! All of the fractions can get a bit confusing, so it really helps to write it out.
If you prefer to watch a video version of this tutorial:
You can also check out more great math tutorials.