Why Do 23 People Usually Include Two With the Same Birthday?

1. Why do 23 people give about even odds of a shared birthday?

Here is the answer first. Pick 23 people at random, ignore the year they were born, and ask whether at least two have the same birthday. The chance is about 50.7% [2]. This is called the birthday problem, or the birthday paradox. It is not a paradox in the sense of a contradiction. It is simply a result that surprises almost everyone, which is why the BBC’s maths writers call it one of “maths’ greatest hits” [1].

The surprise comes from a different question that sounds the same: “Does anyone share my birthday?” Among 23 other people, the chance that someone shares one particular person’s birthday is only about 6.1% (1 − (364/365)²³, which I worked out myself using the formula in source [3]). We tend to imagine ourselves in the room, and for any one person a match is unlikely [1]. But the birthday problem lets any two people match, and that is a much bigger target.

2. What are we really counting when we look for a shared birthday?

Pairs. Your birthday can be compared with 22 other people, so there are 22 chances for a match. But everyone can be compared with everyone. In a group of 23 there are 23 × 22 ÷ 2 = 253 different pairs [2]. That is more than ten times as many chances.

A simple way to picture it is a handshake. In a room of 23 people where everybody shakes hands with everybody else, you personally shake 22 hands, but the room has 253 possible handshakes in total, one for each pair. Each handshake is one pair that might turn out to have the same birthday.

Because the number of pairs grows roughly with the square of the group size, adding a few people adds many pairs. That is why the odds climb so fast. How do we turn this into an exact number, though?

3. How do you calculate the chance that two people share a birthday?

The easiest route is to work out the opposite: the chance that nobody shares a birthday, then subtract it from 1. Assume 365 days, each equally likely, and ignore leap years [2].

• The first person’s birthday can be any day of the year.
• The second person must avoid the first person’s day: 364 out of 365.
• The third must avoid two days: 363 out of 365.
• Keep going to the 23rd person, who must avoid 22 days: 343 out of 365.

Multiply these together and the chance that all 23 birthdays differ is about 0.4927. So the chance that at least two match is 1 − 0.4927 = 0.5073, or 50.7% [2]. With 22 people it is about 47.6% (my own calculation), so 23 is the smallest group that tips past one half. Here is how the chance grows [2]:

So in a class of 30, a shared birthday is more likely than not, and many people call it a coincidence when it is actually the usual outcome [1]. And what if you want a match with you in particular?

4. How many people would you need to have a 50% chance of meeting someone with your birthday?

About 253 other people, the smallest number that pushes the chance just above 50%. The chance that at least one of n other people shares your birthday is 1 − (364/365)ⁿ [3]. I calculated that with n = 252 this is about 49.9%, and with n = 253 it is about 50.05%. So “someone, somewhere, shares a birthday” needs 23 people, while “someone shares mine” needs about 253. The same one-half, a group more than ten times bigger. That gap is exactly the gap between 253 pairs and 22 comparisons.

5. Does the birthday problem work with real people, such as World Cup football squads?

A football World Cup squad has 23 players, and in 2014 there were 32 squads, so it is a tidy test. If the maths holds, about half the squads, 16 of 32, should contain a shared birthday. The BBC checked the official squad lists as of 10 June 2014. It found exactly 16 teams with at least one shared birthday, and five of those had two pairs [1]. Adding the 2010 squads, 31 of 64 squads had a match, still close to half [1].

It is a small test, so some luck is involved, and the BBC itself notes that people argue about whether athletes’ birthdays are truly random [1]. Still, real birthdays are not perfectly even through the year. Does that spoil the calculation? Wikipedia explains that when some birthdays are more common than others, matches become more likely, and that real-world patterns are not uneven enough to move the threshold away from 23 [2]. The textbook calculation also leaves out leap-day birthdays and twins [2], so treat it as a very good model rather than a law.

6. How does the birthday problem matter for computer security?

Computers often squeeze a long file into a short fixed-size “fingerprint” called a hash. Two different files with the same fingerprint (a collision) can be a problem, for example when a fingerprint is used to check a signed contract. If a fingerprint has only 365 possible values, it behaves just like birthdays: after about 23 files, a collision is as likely as not.

Real fingerprints have vastly more values, but the same shape holds. A hash l bits long has 2^l possible values, and a collision turns up with 50% chance after roughly 2^l/2 tries, far fewer than guessing a specific file would need [4]. For a 64-bit hash that is only about 5 billion attempts [4]. Using this fact on purpose is called a birthday attack. It can expose weaknesses in some digital signatures, but according to this page it cannot be used to break an encryption scheme any faster than a brute-force attack [4]. That is one reason designers choose fingerprints that are long.

7. How can you test the birthday problem yourself?

Collect birthdays (day and month only) from a group where everyone is happy to share, such as a class roster that your teacher agrees to read out, or a list of famous people from a book. Do not ask strangers or post anyone’s details online. For groups of about 23 to 30, check each group for a match. Does about half of the groups have a shared birthday? Then pool several groups: if you gather ten groups of 23, you would expect roughly five to contain a match, though luck can easily give you three or seven. If you enjoy numbers, use the multiplication in section 3 on a calculator to confirm the table.