About the Birthday Paradox
The birthday paradox asks: how many people must be in a room before there is a 50% probability that at least two share a birthday? The counterintuitive answer is just 23 — far fewer than most people guess. The probability is computed by calculating the complement: P(no shared birthday) = 365/365 × 364/365 × 363/365 × … × (365−n+1)/365, so P(at least one match) = 1 − P(no match). This calculation belongs to the broader class of collision probability problems, and the same mathematics governs hash collisions in computer science and DNA profiling.
The simulation generates groups of n random birthdays and checks for collisions in real time, accumulating empirical match rates shown as cyan dots on the chart. The red theoretical curve follows the exact formula. Watch how both converge: at n = 23 both reach ~50.7%, and by n = 57 the probability of a shared birthday exceeds 99%. Adjust group size, trials per step, and animation speed to explore the relationship.
Frequently Asked Questions
Why is the answer 23 and not 183 (half of 365)?
People instinctively compare each person to themselves, imagining a 1/365 chance for each new arrival. But 23 people can form 23×22/2 = 253 distinct pairs, and each pair has a 1/365 chance of sharing a birthday. The probability that at least one of 253 pairs matches is much higher than comparing just one person to the room. The rapid growth of the number of pairs is the key insight.
What is the exact formula for the probability?
P(match | n people) = 1 − (365! / ((365−n)! × 365^n)). Equivalently, P(no match) = ∏(k=0 to n−1) (365−k)/365. At n = 23, P(match) ≈ 0.5073 (about 50.7%). At n = 70, P(match) exceeds 99.9%. These numbers assume birthdays are uniformly distributed across 365 days — in reality, birthdays cluster around certain months, which slightly increases the real-world probability.
Where does the birthday paradox appear outside probability puzzles?
The "birthday attack" is a cryptographic attack that exploits collision probability to break digital signatures. If a hash function produces m-bit outputs, a collision can be expected after roughly 2^(m/2) attempts — far fewer than the 2^m trials needed for a brute-force attack. This is why SHA-256 (256-bit outputs) provides only 128 bits of collision resistance, not 256.
Does the paradox assume birthdays are uniformly distributed?
Yes — the formula assumes each birthday is equally likely on any of 365 days (ignoring leap years). In reality, birth rates vary by month and day of week; in many countries there are 10–20% more births in summer months. Non-uniform distributions only increase the probability of a match because collisions are more likely when birthdays cluster. The uniform assumption is therefore conservative.
How many people are needed for a 99% probability of a match?
Just 57 people are needed to achieve a 99% probability, and 70 people to exceed 99.9%. The probability reaches 100% (by the pigeonhole principle) only when n > 365, since at that point two people must share a birthday. In practice the curve is already so steep by n = 60 that it is virtually certain to see a match in any real group of that size.
What if we extend to a year with 366 days?
Including the 29 February (leap day) barely changes the result. The required group size for 50% probability increases from 23 to 24, because the extra possible birthday slightly reduces the collision chance. However, since leap years occur only once every four years and births on 29 February are rare, the practical effect on real-world birthday distributions is negligible.
How is the birthday paradox related to hash tables in computing?
When inserting n items into a hash table with m slots, the probability of at least one collision is approximately 1 − e^(−n²/2m) for large m — the birthday formula in disguise. A hash table with m = 365 slots reaches 50% collision probability at n ≈ 23, exactly matching the birthday problem. This analogy motivates the design of hash functions and the analysis of hash table load factors.
Can we do a three-way birthday match?
Yes — the probability that at least three people in a group share a birthday (a triple match) is much lower than a pairwise match. You need roughly 83–88 people for a 50% chance of a triple match, compared with just 23 for a pairwise match. Generalising further, the group size needed for a k-way match grows approximately as (k! × 365)^(1/k), a much slower growth than the pairwise case.
Why do the empirical dots sometimes differ from the red curve?
Monte Carlo simulation is subject to sampling variance: with few trials, empirical estimates can deviate noticeably from theoretical values. The deviation shrinks as 1/√(trials), so running 10 000 trials halves the typical error compared to 2500 trials. Click "Run 1 000 trials" repeatedly to see the cyan dots converge onto the theoretical red curve.
What is the generalised birthday problem for other "year" sizes?
If days are replaced by any set of d possibilities, the 50% collision threshold occurs at approximately n ≈ 1.18 × √d people. For d = 365 this gives n ≈ 22.5 ≈ 23. For the 2^64 possible SHA-256 truncated outputs used in some applications, a collision is expected after about 2^32 ≈ 4 billion attempts — still far fewer than exhaustive search would require.