Birthday Paradox


The question: What are the chances that two people share a birthday in a group of 23?

In a room of just 23 people there’s a 50-50 chance of two people having the same birthday.

In a room of 75 there’s a 99.9% chance of two people matching.

Put down the calculator and pitchfork, we don't speak heresy. The Birthday Paradox is strange, counter-intuitive, and completely true.

It is only a "paradox" because our brains can not handle the compounding power of exponents.

Our Brains expect probabilities to be linear and only consider the scenarios we are involved in (both faulty assumptions, by the way).

The Birthday Paradox is to find the probability that, in a group of N people, there is at least one pair of people who have the same birthday. See "Same birthday as you" further for an analysis of the case of finding the probability of a given, fixed person having the same birthday as any of the remaining N - 1 people.

How is That?#

In the example given earlier, a list of 23 people, comparing the birthday of:
  • the first person on the list to the others allows 22 chances for a matching birthday,
  • the second person on the list to the others allows 21 chances for a matching birthday
  • third person has 20 chances, and so on.

Hence total chances are:

22+21+20+...+1 = 253

So comparing every person to all of the others allows 253 distinct chances (combinations): in a group of 23 people there are

(23 choose 2) = (23-22)/2 = 253
distinct possible combinations of pairing.

Presuming all birthdays are equally probable, the probability of a given birthday for a person chosen from the entire population at random is 1/365 (ignoring February 29). Although the number of pairings in a group of 23 people is not statistically equivalent to 253 pairs chosen independently, the Birthday Paradox becomes less surprising if a group is thought of in terms of the number of possible pairs, rather than as the number of individuals.

Birthday Attack#

is an attack that depends on the fact that duplicate values, also called collisions, appear much faster than you would expect.

More Information#

There might be more information for this subject on one of the following: