Birthday problem

Birthday problem. The birthday problem, also known as the birthday paradox, is a celebrated result in probability theory that demonstrates how intuitive estimates of likelihood can be surprisingly inaccurate. It examines the probability that, in a set of randomly chosen people, at least two will share the same birthday. The counterintuitive conclusion is that with only 23 individuals, this probability exceeds 50%, a fact first discussed in Richard von Mises and later popularized by William Feller in his seminal text.

Statement of the problem

The classic formulation asks for the minimum number of people required in a room for there to be a greater than 50% chance that at least two share a specific calendar date for their birth, ignoring February 29 and assuming births are uniformly distributed across the 365 days. This problem is a staple in introductory courses on statistics and serves as a compelling introduction to combinatorial probability. Its deceptive simplicity often leads to gross underestimation, making it a favorite pedagogical tool for educators at institutions like Massachusetts Institute of Technology.

Calculating the probability

The standard calculation uses complementary probability. The chance that all *n* people have different birthdays is given by the product of decreasing fractions: 365/365 × 364/365 × ... × (365−*n*+1)/365. Subtracting this product from 1 yields the probability of at least one match. For 23 people, this calculation gives approximately 0.507. This approach relies on principles from combinatorics and was rigorously formalized in works by mathematicians like Pierre-Simon Laplace. The calculations show the probability surpasses 99% with just 57 people, a result frequently demonstrated in textbooks such as those by Sheldon Ross.

Approximations

A well-known approximation uses the Taylor series expansion of the exponential function to estimate the probability as 1 − *e*^(−*n*(*n*−1)/(730)). This derivation connects to the Poisson distribution and provides results very close to the exact calculation for moderate *n*. Another useful rule of thumb, sometimes called the square root approximation, suggests that a 50% probability occurs when the group size is near the square root of 365, or about 19.1, highlighting the order-of-magnitude insight. These approximations are discussed in advanced treatments by authors like Persi Diaconis.

Generalizations

The problem can be generalized to the birthday attack in cryptanalysis, which assesses the likelihood of collisions in hash function outputs, a critical concern for the security of protocols like MD5 and SHA-1. Another generalization considers matches in more than two people, leading to calculations involving the multinomial distribution. The problem also extends to non-uniform birthday distributions, which can be analyzed using techniques from information theory and was studied by researchers at Stanford University. The von Mises birthday problem examines waiting times for a match.

Applications and examples

Beyond pure mathematics, the birthday problem has direct applications in computer science, particularly in designing randomized algorithms and analyzing cryptographic systems vulnerable to collision attacks. It models real-world phenomena like the probability of shared anniversaries in a large corporation or matching serial numbers in manufacturing. The principle is famously used to explain the likelihood of coincidences in large datasets, a concept explored by scientists like Stephen Stigler. Its implications are taught globally in curricula from the Indian Statistical Institute to Harvard University.