# 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!

*Appendix*

*Using experiments, events and sample spaces to solve the Birthday Problem.*

Another way to look at the Birthday problem is by use of experiments and sample spaces. A sample space lists the possible outcomes of an experiment.

Take a coin-tossing experiment. In this case, a coin is tossed and it can land heads or tails.

Experiment: Toss a coin. Sample space = Heads; Tails.

Experiment: Toss a coin until it get Heads. Identify the number of tosses needed. Sample space = 1; 2; 3; 4; 5.

Experiment: Measure the time between two successive lightning strikes. Sample space = the set of positive numbers.

In many common examples, each outcome in the sample space is assigned an equal probability. An example is tossing a coin twice.

Here, the sample space = HH, HT, TH, TT.

Assign an equal probability to each of these outcomes. So, probability of each outcome = 1/4.

An ‘event’ is the name for a collection of outcomes.

The probability of an event = number of outcomes in the event / number of outcomes in the sample space.

Event of zero heads (TT) has probability = 1/4

Event of exactly one heads (HT, TH) has probability = 2/4 = 1/2

Event of two heads (HH) has probability = 1/4

Examples from dice (plural); die (singular). Sample space from one die = 1, 2, 3, 4, 5, 6.

Possible events:

a. Outcome is number 5

b. Outcome is an even number.

c. Outcome is even but is less than 6.

In a., probability = 1/6

In b., probability = 3/6

In c., probability = 2/6

Now, apply these concepts to the Birthday Problem.

Suppose that a room contains four people. What is the probability that at least two of these people share the same birthday?

The easiest way to solve this is to count the complementary event that none of the four share the same birthday and find that probability. We can then subtract this probability from 1 to establish the probability that at least two of the four share a birthday.

Size of the sample space = 365 x 365 x 365 x 365

Size of event that none of the four share the same birthday = 365 x 364 x 363 x 362

Probability that none of the four people share the same birthday =

365 x 364 x 363 x 362 / 365 x 365 x 365 x 365 = 0.984

Probability that at least two of them share the same birthday = 1 – 0.984 = 0.016

Similarly, it can be calculated that the probability of at least two sharing a birthday increases as n, the number in the room, increases, as below:

n = 16; probability = 0.284

n= 23; probability = 0.507

n = 32; probability = 0.753

n = 40; probability = 0.891

n= 56; probability = 0.988

n = 100; probability = 0.9999997

So, the probability that two share a birthday exceeds 0.5 in a room of 23 or more people.