The Birthday Paradox
How many people do you need in a room before there is a greater than 50% chance that two share the same birthday? Surprisingly few, as it happens.
The birthday paradox (also known as the birthday problem) is a counterintuitive concept in probability theory that deals with the likelihood of two people sharing the same birthday within a group of people. Despite its name, it’s not actually a paradox but rather a surprising result.
The common intuition might be that the probability of two people sharing the same birthday is quite low, considering there are 365 days in a year (ignoring leap years for simplicity). However, the counterintuitive result is that in a group of just 23 people, there is a better than even chance (greater than 50%) that at least two of them share the same birthday.
This paradox arises from the fact that there are many possible pairs of people in a group, and each pair has a chance of having the same birthday. As the group size increases, the number of potential pairs increases exponentially, leading to a higher probability of a shared birthday.
The probability calculations take into account the complement (the probability that no one shares a birthday) and use the fact that 1 minus the probability of the complement gives the probability of the event occurring.
By the time the number of people in the room has hit 57, there is a 99% probability that two will share the same birthday, and by the time there are 100, there is only a 1 in 3 million chance that no one shares a birthday. Thanks to what’s referred to as the “pigeonhole principle”, the probability reaches 100% when the number of people hits 367 (since there are only 366 possible birthdays, including 29 February).
This phenomenon is often used to illustrate concepts in probability and has practical applications in cryptography, hashing algorithms and other fields.
The mathematics behind this problem led to a well-known cryptographic attack called the birthday attack, which uses this probabilistic model to reduce the complexity of cracking a hash function. Using the birthday paradox, hackers developed an algorithm to more quickly cause hash collisions and ultimately crack one of the most widely used cryptographic algorithms of its time. This hole has since been plugged.
The paradox/problem is generally thought to have been discovered by English mathematician Harold Davenport in about 1927, though he did not publish it at the time. Davenport did not claim to be its discoverer because he “could not believe that it had not been stated earlier”. The first publication of a version of the birthday problem was by Austrian scientist and mathematician Richard von Mises in 1939.
If you would like to better understand the maths, check out an entertaining video explanation by Michael Stevens, an American educator, speaker and editor best known for creating and hosting the YouTube channel Vsauce.
Story Idea: Alex McGowan (contributed during a sauna session at the Bondi Icebergs Pool)
Video
REMORANDOM Book Chapter
