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 having 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 February 29).
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 attributed to 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 this 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)
_________________________
References
wikipedia.org/wiki/Birthday_problem
wikipedia.org/wiki/Michael_Stevens_(educator)
Images
1. Lola Giuffré "celebrates" turning 4 in New York City on 20 March 1999
2. Graphs showing the approximate probabilities of at least two people sharing a birthday (red) and its complementary event (blue)
3. Table shows the probability for some other values of (ignoring leap years)
4. Pigeons in holes. Here there are n = 10 pigeons in m = 9 holes. Since 10 is greater than 9, the pigeonhole principle says that at least one hole has more than one pigeon. (The top left hole has 2 pigeons.)
5. Harold Davenport in 1931. Source: archives of P. Roquette, Heidelberg.
6 & 7. Video: The Birthday Paradox, Michael Stevens, Vsauce2
8. Michael Stevens
