# The Birthday Problem

How large should a randomly chosen group of people be, to make it more likely than not that at least two of them share a birthday?

For convenience, assume that all dates in the calendar are equally likely as birthdays, and ignore the Leap Year special of February 29^{th}

The first thing to look at is the likelihood that two randomly chosen people would share the same birthday.

Let’s call them Fred and Felicity. Say Felicity’s birthday is May 1^{st}. What is the chance that Fred shares this birthday with Felicity? Well there are 365 days in the year, and only one of these is May 1^{st} and we are assuming that all dates in the calendar are equally likely as birthdays.

So, the probability that Fred’s birthday is May 1^{st} is 1/365, and the chance he shares a birthday with Felicity is 1/365.

So what is the probability that Fred’s birthday is not May 1^{st? }It is 364/365. This is the probability that Fred doesn’t share a birthday with Felicity.

More generally, for any randomly chosen group of two people, the probability that the second person has a different birthday to the first is 364/365.

With 3 people, the chance that all three are different is the chance that the first two are different (364/365) multiplied by the chance that the third birthday is different (363/365).

So, the probability that 3 people have different birthdays = 364/365 x 363/365

This can be written as (364)_{2 }/ 365^{2}

Similarly, probability that 5 people have different birthdays = (364)_{4} / 365^{4}

= 364x363x362x361/365^{4}

So far, the chance of no matches is very high. But by the tenth person the probability of no matches is:

(364/365)*(363/365)(362/365)*(361/365)(360/365)*(359/365)(358/365)*(357/365) (356/365) = 0.8831

More generally, for n people, probability they all have different birthdays =

(364)_{n-1 } / 365^{n-1}

For 23 people, probability of all different birthdays = (364)_{22 }/ 365^{2} = 0.4927

For 22 people, probability of all different birthdays = (364)_{21 }/ 365^{2} = 0.5243

So, in a group of 23 people, there is a (1-0.4927) = 0.5073 chance of that at least two of the group share a birthday.

So how large should a randomly chosen group of people be, to make it more likely than not that at least two of them share a birthday? The answer is 23.

The intuition behind this is quite straightforward if we recognise just how many pairs of people there are in a group of 23 people, any pair of which could share a birthday.

In a group of 23 people, there are, according to the standard formula, ^{23}C_{2 }pairs of people (called 23 Choose 2) pairs of people.

Generally, the number of ways k things can be chosen from n is:

^{n} C _{k} = n! / (n-k)! k!

Thus, ^{23}C_{2 }= 23! / 21! 2! = 23 x 22 / 2 = 253

So, in a group of 23 people, there are 253 pairs of people to choose from.

_{ }Therefore, a group of 23 people generates 253 chances, each of size 1/365, of having at least two people in the group sharing the same birthday.

These chances have some overlap: if A and B have a common birthday, and A and C have a common birthday, then inevitably so do B and C. So the probability of at least two people sharing a birthday in a group of 23 is less than 253/365 (69.3%). It is, as shown previously, 50.73%.

To conclude, the next time you see two football teams line up, include the referee. It is now more likely than not that two of those on the pitch share the same birthday. Strange, but true!