The Birthday Problem


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
Rearranging:
P(birthday match exists) = 1 – P(no birthday matches)
So
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.

Factorials

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: 1*2*…*(365-n)*(365-n+1)*…*(365-1)*365/1*2*…*(365-n)

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.

Leave a comment



toronto tutor team

Contact Info

Ready to start learning? Give us a call or send us an email to book a tutoring session today.

+1 855-775-4473
info@torontotutorteam.ca

Use the message icon below to live chat with a member of the Team right now!

Copyright 2016 © All Rights Reserved