The Birthday Problem

One version of the birthday problem is as follows:

How many people need to be in a room such that there is a greater than 50% chance that 2 people share the same birthday.

This is an interesting question as it shows that probabilities are often counter-intuitive. The answer is that you only need 23 people before you have a 50% chance that 2 of them share a birthday. So, why do you only need 23 people?

The key to understanding this question is realising that when comparing if any of the (n) people in the room share a birthday, you are not simply making n comparisons – but C(n,2) (n choose 2) comparisons. If there are people A, B, C and D in a room I don’t just make 4 comparisons,  I have to compare AB, AC, AD, BC, BD, CD. This is the same calculation as working out 4 choose 2 = 6 comparisons.

Therefore when there are 23 people in the room you actually need to make C(23,2) comparisons = 253. This goes someway to explaining why the number is much lower than you would expect – but it still doesn’t tell us where the number 23 came from.

If we simplify things so that we don’t have leap years then we can approximate the problem by working out the probability p(no shared birthday). When there are 2 people in the room the probability that person B does not share his birthday with person A is 364/365. When a third person enters the room the probability that C doesn’t share his birthday with A or B is 363/365. Carrying on in this manner, when the 23rd person enters the room, the probability that he doesn’t share a birthday with anyone already there is 343/365.

We then work out p(no shared birthday) = 364/365 x 363/365…x 343/365 = 0.4927
So p(shared birthday) = 1 – 0.49 = 0.51 (2 dp).  Therefore when there are 23 people in the room the probability of a shared birthday is around 51%.

However, the method outlined above is a little unsatisfactory – as we start by using the fact that we know the answer is 23 and then work backwards.  So how can we discover the result independently? One possibility is to use the Poisson approximation, P(λ):

(where X is the number of shared birthdays).  If we want the probability of at least 1 shared birthday then we can find 1 – P(X=0).  When k = 0 the formula reduces to e.  Therefore P(X>0) = 1 – e

So, if we want the probability to be greater than 0.5 we can then set up an inequality and solve:

1 – e  > 0.5
0.5 > e
ln(0.5) > – λ

Next we use the fact that λ is the expected value – and so will be given by C(n,2)/365.  This is because the number of potential birthday combinations divided by 365 will give us the mean number of shared birthdays.  We also use the formula for C(n,r) which is n!/(k!(n-k)!).  This gives C(n,2) = n(n-1)/2

-ln(0.5) < C(n,2)/365
253 < C(n,2)
253 < n(n-1)/2
0 < n2 – n – 506

Which we can solve using the quadratic formula to give n = 23 almost exactly.

You can also extend the problem by looking at the probabilities at least 3 people have the same birthday. Wolfram Alpha have an online generator to allow you to do this.

If you liked this post you might also like:

The Gorilla in the Room and other Great Maths Investigations – some great ideas for statistics investigations and good links to maths ToK – can we believe our senses?

How Are Prime Numbers Distributed? Twin Primes Conjecture. Discussion on studying prime numbers – in particular the conjecture that there are infinitely many twin primes.