Paradox Compilation

The Birthday Paradox

In probability theory, the birthday problem or birthday paradox concerns the probability that, in a set of N randomly chosen people, some pair of them will have the same birthday. By the pigeonhole principle, the probability reaches 100% when the number of people reaches 367 (since there are 366 possible birthdays, including February 29). However, 99.9% probability is reached with just 70 people, and 50% probability with 23 people. These conclusions include the assumption that each day of the year (except February 29) is equally probable for a birthday. The history of the problem is obscure. W. W. Rouse Ball indicated (without citation) that it was first discussed by Harold Davenport. However, Richard von Mises proposed an earlier version of what we consider today to be the birthday problem.

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 finding a collision for a hash function.

This is not a paradox in the sense of leading to a logical contradiction, but is called a paradox because the mathematical truth contradicts naive intuition: an intuitive guess would suggest that the chance of two individuals sharing the same birthday in a group of 23 is much lower than 50%, but the birthday problem demonstrates that this is not the case.