Birthday paradox

How many people have to be in a classroom or at a party for there to be at least a 50% chance that two of them share a birthday? We ignore the year and only count the day and month. For most people, intuition suggests something around 183, that is, half the year. The correct answer is 23.

It is only a paradox on the surface. There is no contradiction here, it is just that our intuition pulls us in completely the wrong direction.

Why so few?

When we ask about sharing a birthday, we usually think of ourselves: does anyone have the same birthday as me? But the question is aimed elsewhere. We are not looking for a match with me, but for a match between any two people in the group.

A group contains far more pairs than you might expect. In a group of 23 people, each person can form a pair with 22 others. That gives 23 · 22, but we have counted every pair twice (Oliver with Amelia and Amelia with Oliver), so the number of pairs is

$$\frac{23\cdot 22}{2}=253.$$

This is the same as the binomial coefficient $(\genfrac{}{}{0ex}{}{23}{2})$. Each pair gives one chance of a match, and 253 attempts is quite a lot.

How to work it out

Let’s assume that a year has 365 days, we leave out 29 February, and every day is equally likely. In reality the number of births varies slightly through the year, but this hardly affects the result.

Calculating directly when at least two people share a birthday would be hard work. Two people could match, or three, or two different pairs… So we take a detour through the complementary event: we work out the probability that everyone has a birthday on a different day, and subtract it from one.

We start with three people. The first can have a birthday on any day, which is $\frac{365}{365}$. The second has to land on a different day from the first, so only 364 days out of 365 are left. For the third, both days already taken are ruled out, so there are 363 days to choose from. We multiply the probabilities:

$$\frac{365}{365}\cdot \frac{364}{365}\cdot \frac{363}{365}\approx 0.9918$$

The probability that two of the three people share a birthday comes out as 1 − 0.9918 = 0.0082, which is less than one per cent.

For 23 people the method is the same, there are just more fractions. The twenty-third person has 365 − 22 = 343 days to choose from:

$$\frac{365}{365}\cdot \frac{364}{365}\cdot \frac{363}{365}\cdot \dots \cdot \frac{343}{365}\approx 0.4927$$

With a probability of about 0.4927, everyone has a birthday on a different day. We subtract this from one:

$$1-0.4927=0.5073$$

The probability that at least two of the 23 people share a birthday is about 50.7%. With 22 people it is still only 47.6%, so 23 is the smallest number for which the chance goes above a half.

With every extra person the probability rises quickly. For 10 people it comes out at about 12%, for 30 about 71%, for 50 about 97%, and for 70 it is already over 99.9%. If thirty children sit in a class and no two of them share a birthday, that is, if anything, a bit of luck.

What about my birthday?

Let’s go back to the question that occurs to people first: how many people are needed for at least one of them to have the same birthday as me?

This is calculated differently. Each of n people has a birthday on a different day from mine with probability $\frac{364}{365}$, independently of the others. We want

$$1-{\left(\frac{364}{365}\right)}^n\ge \frac{1}{2}.$$

For n = 252 we get about 0.4991, which is still not enough. For n = 253 we get about 0.5005, so we need 253 people. Incidentally, that is exactly the number of pairs in a group of 23 people. It is not entirely a coincidence: 253 pairs are 253 chances of a match, just like 253 people compared with me. But getting exactly the same number is partly down to luck. The pairs also influence each other a little, which is why 23 people give 50.7% and not 50.05%.

See also

• Complementary event
• Probability
• Combinations
• Monty Hall problem