The Birthday Paradox: 23 People, 253 Pairs, and a 50.7% Chance of a Match

The setup, the assumptions, and the exact answer

The birthday problem asks: given n people, what is the probability that at least two of them share a birthday? The classical answer rests on three hypotheses, and they matter:

• 365 possible days — February 29 is dropped.
• Each day equally likely — birthdays are uniform on those 365 days.
• Independence — one person's birthday tells you nothing about another's, so no twins or other multiple births in the room.

Under those hypotheses the clean quantity is the complement: the probability that all n birthdays are distinct. Line the people up. The first person may take any day. The second must dodge one taken day, leaving 364 of 365. The third must dodge two, leaving 363 of 365. In general:

P(all distinct) = (365/365) × (364/365) × (363/365) × ⋯ × ((365−n+1)/365) = 365! / (365ⁿ (365−n)!)

and P(at least one match) = 1 − P(all distinct). Evaluating it:

• n = 22: P(all distinct) = 0.524305, so P(match) = 47.57% — still under a half.
• n = 23: P(all distinct) = 0.492703, so P(match) = 50.73% — over the half.

So 23 is the first group size at which a shared birthday is more likely than not, and the crossing is genuinely narrow: one extra person moves the probability by 3.16 percentage points and that is exactly enough. The product above is an exact theorem given the three hypotheses, not an approximation; everything downstream in this article is either that product or a bound on it.

Why it feels wrong: people crawl, pairs explode

Almost everyone who is surprised by 23 has silently answered a different question: how many people do I need before someone shares my birthday? That probability is 1 − (364/365)ⁿ, and it does not reach a half until n = 253. The gap between 23 and 253 is the whole illusion.

The birthday problem is not about you. It is about pairs. A room of n people contains C(n,2) = n(n−1)/2 pairs, and each pair is a separate chance to collide:

• 5 people → 10 pairs
• 10 people → 45 pairs
• 23 people → 253 pairs
• 50 people → 1,225 pairs

Adding the 23rd person adds 22 new pairs at once. The head count grows linearly, the pair count quadratically, and the eye tracks the head count. A quick sanity estimate: each pair matches with probability 1/365, so the expected number of matching pairs among 23 people is 253/365 = 0.6932. An expectation near 1 already says ‘a match is an ordinary event here’, long before any product is computed.

Note what that expectation is not: it is not a probability, and the 253 pair-events are not independent (if A matches B and B matches C, then A matches C). What saves the estimate is that the dependence is weak; the Poisson approximation 1 − e^−0.6932 = 0.5000 lands within 0.8 percentage points of the true 0.5073. In Quine's taxonomy this makes the birthday paradox a veridical paradox: the conclusion is genuinely true and genuinely counterintuitive, not a contradiction hiding a flaw.

The falling product and the exponential shortcut

Write the product in the form that shows why it collapses:

P(all distinct) = ∏_k=0ⁿ⁻¹ (1 − k/365)

Each new arrival multiplies in a factor slightly below 1, and the factors get worse as the room fills: the 23rd person contributes 343/365 = 0.9397. Twenty-three mild discounts compound into a near-halving.

Because 1 − x ≤ e^−x for all real x, the whole product is bounded:

P(all distinct) ≤ exp(−(0+1+⋯+(n−1))/365) = exp(−n(n−1)/730)

which turns into a rigorous lower bound on a match: P(match) ≥ 1 − e^{−n(n−1)/730}. At n = 23 the exponent is 253/365 = 0.693151, and ln 2 = 0.693147. The two agree to five decimal places, so the approximation returns e^{−ln 2} = 0.50000 almost exactly — a numerical coincidence that makes 23 look like a designed answer. The true value, 0.5073, is slightly larger, exactly as the inequality demands.

How good is the shortcut in general?

• n = 10: exact 11.69%, approximation 11.60%
• n = 23: exact 50.73%, approximation 50.00%
• n = 40: exact 89.12%, approximation 88.20%

It always understates the chance of a match, and the error peaks in the middle of the transition. Use the exact product when you need the number; use the exponential when you need the scaling law.

The square-root law: how the threshold scales with d

Replace 365 by a general number of equally likely days d. Setting 1 − e^−n²/(2d) = 1/2 and solving gives the standard estimate for the 50% threshold:

n₅₀ ≈ √(2d ln 2) = 1.1774·√d

For d = 365 that is 22.49, which rounds up to the correct 23. The headline is the √d: to make collisions twice as hard to find you must make the calendar four times longer. Some values:

• d = 100 → estimate 11.8, exact threshold 13
• d = 365 → estimate 22.5, exact threshold 23
• d = 1,000 → estimate 37.2, exact threshold 38
• d = 2⁶⁴ → estimate 5.1 × 10⁹ (the exact threshold is indistinguishable at this scale)

Treat that formula as asymptotic rather than exact: it runs one or two people low for small d — it returns 11.8 where the true answer is 13 — because it replaces n(n−1) by n² and leans on the e^−x bound. Its relative error vanishes as d grows, which is why cryptographers use it without apology at d = 2⁶⁴.

A closely related and often-confused quantity is the expected number of people you must poll before the first repeat appears. That is 1 + Q(d), where Q is Ramanujan's Q-function, Q(d) ≈ √(πd/2) − 1/3. For d = 365 the exact sum Σ_k≥0 P(no match among k) gives 24.6166 people on average — larger than the median-style threshold of 23, because the distribution of the first repeat has a long right tail.

Real birthdays are not uniform — and that only helps the match

The uniform-day hypothesis is false in the real world, so the honest question is which way the error points. The answer is a theorem, not a guess. D. M. Bloom proved in 1973 (A Birthday Problem, American Mathematical Monthly 80, 1141–1142) that among all distributions on d days, the uniform one minimises the probability of a match. Formally, for any probability vector p on the days, P(match among n) ≥ the uniform value, with equality only for the uniform p. The mechanism is convexity: the collision probability for a single pair is Σ p_i², which is minimised at p_i = 1/d by Cauchy–Schwarz, and the same Schur-convexity argument extends to n people.

So 23 is a worst case. Any real seasonality can only push the threshold down or leave it alone.

How big is the real-world skew? In US births from 1994 to 2014, mid-September is the peak — September 9 is the single most common date — while December 25, January 1 and (excluding February 29) the days around major holidays are the rarest, largely because scheduled inductions and Caesareans are moved off those dates. The swing is larger than people expect — the September peak runs close to twice the Christmas Day trough — and it is still far too small to move the threshold. The reason is that the quantity that matters is the single-pair collision probability Σ p_i², and a spread of that shape raises it by well under one percent: it is equivalent to shortening the calendar from 365 days to about 363. Computations on empirical birth frequencies (Munford 1977; Nunnikhoven 1992) accordingly still return 23.

Leap years behave the same way: give February 29 weight 1/1461 and the other days 4/1461 each, and the 50% threshold is still 23. Independence is the hypothesis most likely to fail in practice — a room containing twins, or any multiple birth, has a strictly higher match probability than 50.73%, which is again an increase, not a decrease.

Variants: near-matches, triples, and everybody-matched

The same machinery answers a family of related questions, and the answers are worth memorising because they are often misquoted.

Question	People needed for 50%
Two people share a birthday (the classic)	23
Someone shares one specified date (e.g. yours)	253
Two birthdays fall within one day of each other	14
Three people share the same birthday	88
Every person shares with somebody (strong birthday problem)	3,064

The 253 coincidence. Solving 1 − (364/365)ⁿ ≥ 1/2 gives n ≥ 252.65, so 253 people are needed for an even chance that someone matches a fixed date. That 253 is numerically identical to C(23,2), the pair count at the classic threshold. The coincidence is real but not deep: both arise from 365·ln 2 ≈ 253.

Near-matches. Abramson and Moser (More Birthday Surprises, American Mathematical Monthly 77, 1970, 856–858) showed that if ‘match’ is loosened to ‘within one day’, only 14 people are needed. Loosening to within a week takes it down to 7. This is why ‘amazing coincidences’ at parties are cheap: fuzzy matching multiplies the number of ways to succeed.

Triples. Requiring three people on one date raises the bar to 88, and four people to about 187 — the threshold for a k-fold collision scales like d^(k−1)/k, so it climbs quickly but far more slowly than most people expect.

The certain end. With 366 people the pigeonhole principle forces a shared birthday with probability 1 (367 if February 29 is admitted). Note the shape of the curve: 50% at 23, 99.01% at 57, 99.92% at 70, and then a long flat crawl of 300 more people to reach certainty.

Where the birthday bound bites: hashing, IDs, and cryptography

Every hash function is a calendar with a very large number of days. A b-bit digest has d = 2^b possible outputs, so if it behaves like a uniform random map, a collision becomes more likely than not after about 1.1774·√(2^b) ≈ 2^b/2 hashed items. This birthday bound is why ‘collision resistance’ is always advertised at half the digest length.

• 32-bit checksum: 50% collision chance after ~77,000 items — hopeless for deduplication.
• 64-bit hash: ~5.1 × 10⁹ items. A large data-warehouse key space reaches this.
• UUIDv4 (122 random bits): ~2.7 × 10¹⁸ UUIDs, which is why random UUIDs are safe in practice.
• MD5 (128-bit): generic birthday cost 2⁶⁴. In practice it fell far below that — Wang, Feng, Lai and Yu announced practical collisions in August 2004 (published at Eurocrypt 2005) that are found in minutes, and the Flame malware (2012) used a chosen-prefix MD5 collision to forge a Microsoft code-signing certificate.
• SHA-1 (160-bit): generic birthday cost 2⁸⁰. The SHAttered attack (Stevens, Bursztein, Karpman, Albertini and Markov, announced 23 February 2017) produced two colliding PDFs using about 2^63.1 SHA-1 compressions — roughly 6,500 CPU-years plus 110 GPU-years of computation.

Two cautions. First, the birthday bound is an upper bound on the work a generic attacker needs; cryptanalysis routinely beats it, as both MD5 and SHA-1 show, so 2^b/2 is a ceiling on security, never a floor. Second, it assumes outputs are uniform and independent — a biased or structured hash collides sooner, and by Bloom's theorem never later.

The same √d shows up wherever collisions are the point rather than the hazard: Pollard's rho algorithm solves a discrete logarithm in a group of order n in O(√n) steps, and factors an integer N in about O(N^1/4) steps — the collision it hunts for is a birthday collision in a pseudorandom walk, taken modulo the smallest prime factor — and load-balancing analyses use it to predict when two keys land in the same bucket.

How the birthday probability climbs as the room fills (365 equally likely days)

People n	Pairs n(n−1)/2	P(no shared birthday)	P(at least one match)
10	45	0.8831	11.69%
20	190	0.5886	41.14%
23	253	0.4927	50.73%
40	780	0.1088	89.12%
57	1596	0.0099	99.01%