Twenty-three people

There are 365 days in a year. How many people must be in a room before it is more likely than not that two of them share a birthday?

The number most people offer is around 180 — half of 365, on the reasoning that a shared birthday needs the days to be about half used up. The correct answer is 23, and the gap between the guess and the answer is one of the more reliable demonstrations that intuition about probability is not merely imprecise but systematically wrong in a particular direction.

Counting the other way #

The direct calculation is unpleasant: a shared birthday could involve any pair, or several pairs, or three people at once, and adding those cases up means counting some of them twice.

The complementary calculation is easy. Instead of asking how likely a match is, ask how likely it is that everyone is different — and that has a single clean answer, because the people can be dealt with one at a time.

The first person takes some day. The second must avoid it: $364/365$. The third must avoid two days: $363/365$. And so on, so that the chance of $k$ people all differing is

$$\frac{364}{365} \times \frac{363}{365} \times \cdots \times \frac{365-k+1}{365}.$$

At $k = 23$ this product falls to $0.4927$, so the chance of a match is $0.5073$ — just over a half. At $k = 22$ it is $0.4757$, just under.

Twenty-three is where it crosses, and the generator finds the crossing rather than being told it: it evaluates the product at every group size and locates the first that reaches a half, then asserts that $22$ is below and $23$ is above. A figure that merely marked the famous number would be decoration.

Counting the complement is the move, and it is worth naming because it works far more often than it is reached for. At least one is almost always harder than none, since at least one has cases and none has a single path.

Why twenty-three and not a hundred and eighty #

The intuition fails because it answers a different question, and the difference is worth stating precisely.

Does someone share my birthday? Each other person has one chance in 365, so about 253 people are needed for that to be more likely than not. The naive guess is a poor answer to this question.

Do any two share a birthday? Every pair is a chance, and a group of $k$ has $\binom{k}{2} = k(k-1)/2$ pairs.

That count grows quadratically. Ten people make 45 pairs; twenty-three make 253; fifty make 1,225. Doubling the room roughly quadruples the opportunities, and the number of pairs overtakes the number of days far earlier than the number of people does.

That is worth stating as the actual diagnosis. The naive guess is not a failure of arithmetic; it is an answer to does anyone match me, which is the question a person in the room would naturally ask, and which scales linearly. The birthday problem asks a question about the room rather than about a person, and the room’s structure is combinatorial in a way that pictures of the room do not display.

That coincidence is worth a sentence, because it is the clearest way to see what is going on. Twenty-three people contain 253 pairs; 253 is also the number of people needed for someone to probably share a specific birthday. The two questions need the same number of chances — it is just that in one case the chances are people and in the other they are pairs, and pairs accumulate much faster.

The rough rule, and where it holds #

A back-of-the-envelope version explains the shape of the answer.

With $n$ pairs each having a $1/365$ chance of matching, and treating them as independent, the chance of no match is about $(1 - 1/365)^n \approx e^{-n/365}$. Setting that to a half gives $n \approx 365 \ln 2 \approx 253$ pairs, which needs $k \approx \sqrt{2 \times 253} \approx 22.5$ people.

The $\ln 2$ appearing there is not decoration either: it is where a halving becomes an exponent, and it arrives for the same reason it arrives in any process governed by proportional decay — the chance of no match falls exponentially in the number of pairs, and asking when it reaches a half is asking for a logarithm.

So the answer scales as the square root of the number of days:

$$k \approx 1.18\sqrt{d}.$$

That is the fact worth carrying, because it transfers to every collision problem there is. A hundred times as many days needs only ten times as many people.

The independence assumption is false — whether Alice and Bob match is not independent of whether Bob and Carol do — and the approximation is nonetheless excellent, because the dependence is weak when matches are rare. That is the usual situation with such estimates, and the usual trap: the rule is reliable in the regime where collisions are unlikely and degrades exactly where they become common.

How many matches, rather than whether #

Asking whether there is a match throws away information, and the discarded part explains the answer better than the kept part does.

The expected number of matching pairs is easy, because expectations add whether or not the things added are independent — the same fact that made Barbier’s theorem work on a bent needle. Each of the $\binom{k}{2}$ pairs matches with probability $1/365$, so the expected count is simply

$$\frac{k(k-1)}{2} \cdot \frac{1}{365}.$$

At $k = 23$ that is $253/365 = 0.693$. Which is $\ln 2$, to three places, and that is not a coincidence: the crossing point was defined by the condition $e^{-\text{expected}} = \tfrac12$, and $\ln 2$ is what makes that true.

The number of matches behaves almost exactly like a Poisson count with that mean, so the chance of no match is about $e^{-0.693} = 0.500$. The exact answer is $0.4927$, so the approximation is out by less than a percentage point.

Reading it this way makes the whole problem less surprising. At 23 people there are about $0.69$ matches expected — not zero, not two, but a number comfortably of order one. Anyone who had computed the expected count first would never have guessed 180, because 180 people give an expected 44 matching pairs, which is not a borderline case but a certainty many times over.

The expectation was the easy calculation and the informative one, and the famous version of the question asks for neither.

Where the same arithmetic bites #

The square-root scaling is not a curiosity about parties. It is the reason a cryptographic hash needs to be twice as long as a first reading suggests.

A hash function turns a document into a fixed-length fingerprint. Its security requires that nobody can find two documents with the same fingerprint — a collision.

With an $n$-bit hash there are $2^n$ possible fingerprints. Finding a document matching one specific fingerprint takes about $2^n$ attempts, which for $n = 128$ is beyond any conceivable machine. But finding any two documents that match each other is the birthday problem, and takes about $2^{n/2}$ attempts — the square root.

So a 128-bit hash offers 128 bits of resistance against the first attack and only 64 against the second. Sixty-four bits is roughly $1.8 \times 10^{19}$ operations, which is expensive and has been done. This is why hash outputs are sized at twice the security level wanted, and why the birthday problem appears in the first chapter of every cryptography text.

The attack is practical rather than theoretical. Generate a large batch of harmless-looking documents and a large batch of malicious ones, hash them all, and look for a match across the two sets. Sign the harmless one and the signature is equally valid on the malicious one. This is how MD5 was broken in practice, and colliding files — two PDFs with identical hashes and different contents — have been published.

There is a memory cost hiding in that description, and it is the reason the attack is not quite as cheap as the operation count suggests. Storing $2^{n/2}$ hashes to look for a repeat needs $2^{n/2}$ of storage, which for a 128-bit hash is $2^{64}$ entries and not available. The practical version — Pollard’s rho — trades that away, finding collisions in the same number of operations and almost no memory, by following a single long chain and waiting for it to run into itself. It is the same principle applied to a walk rather than a set, and the walk’s return to a previous state is the collision. Which is the repeating-decimal argument again: finitely many states, so a path must revisit one.

What the assumptions are worth #

The calculation assumes birthdays are uniform across 365 days and independent between people, and neither is quite true.

Real birth dates are not uniform. September is busier than February in most northern-hemisphere countries; birth rates dip at weekends and on public holidays, because scheduled deliveries avoid them. And 29 February exists.

Both of these push the answer in the same direction, and the direction is worth knowing: any deviation from uniformity makes matches more likely, never less. Concentrating births into fewer effective days is exactly what shortens the time to a collision. So 23 is an upper bound, and the true figure for a real population is 23 or slightly less — measurements put it at 23 still, since the non-uniformity is mild.

The independence assumption fails for twins, and a room containing a pair of them has a match with certainty. That is not a small correction in a small group, and it is the sort of structure that makes the theoretical answer a poor guide to a particular room.

It is worth noting how the leap year behaves, because the instinct is that it must matter and it does not. Adding a 366th day that occurs a quarter as often changes the effective number of days by a fraction of a percent, and the threshold is unmoved — the crossing is still at 23, with the probability shifting in the fourth decimal place. The square-root scaling is why: a quantity that goes as $\sqrt{d}$ barely notices a change in $d$ of one part in fifteen hundred. Robustness of that kind is worth checking rather than assuming, and here the check is that the answer depends on the square root of an input, which is the cheapest kind of dependence there is.

The uniformity assumption deserves the same treatment as the needle-dropping estimate’s independence assumption: it is the clause a real experiment violates, it pushes the answer in a knowable direction, and the size of the push is worth computing rather than worrying about.

What the picture cannot show #

The curve is a probability, and a probability is a statement about an ensemble of rooms rather than about any room. A group of 23 with no shared birthday has not contradicted anything, and neither has a group of 5 with one. Nothing observable in a single case bears on the claim, and the figure is drawing a quantity no one experiment can measure.

The pictures are also silent about the shape of the surprise. What makes this problem famous is the discrepancy between the answer and the intuition, and the intuition’s error is a psychological fact about which question people hear. A curve passing through a half at 23 does not display that error, because the error is in the reader’s head and the curve knows nothing about it.

There is one thing the figures do establish, and it is worth crediting: the curve is nearly flat past 50, which shows that the exact threshold hardly matters. Asking for 90% instead of 50% moves the answer from 23 to 41, not to 300. The steepness is where the whole story is, and the steepness is visible.

The ladder from here #

Rungs above: the near-birthday problem, where two people within a day of each other need only 14. The generalised collision bound, $\sqrt{2d\ln(1/(1-p))}$, derived. Non-uniform birthdays, with the theorem that any deviation lowers the threshold. The coupon collector problem, which is the same setup asked backwards and where the harmonic series appears. Birthday attacks on hash functions in detail, with the meet-in-the-middle structure. Pollard’s rho algorithm, which uses collisions deliberately to factor integers. The Poisson approximation to the number of matches. And the pigeonhole principle, which answers the certainty version of this question: 367 people guarantee a match, and the gap between 23 and 367 is the gap between probably and certainly.

Probably against certainly #

That last comparison is the most useful thing here, and it is a distinction the two essays make from opposite sides.

Pigeonhole says: with 367 people, a shared birthday is guaranteed. No probability, no assumptions about uniformity, no way out. It is a counting fact.

This essay says: with 23 people, a shared birthday is more likely than not. It assumes a distribution, it can be wrong about any particular room, and it arrives at its answer sixteen times sooner.

Both are correct and they answer different questions, and confusing them is a standard error in both directions. Someone who knows only the pigeonhole version will vastly overestimate how many people a match needs. Someone who knows only the probabilistic version may treat 23 as a guarantee, which it is not — a room of 23 goes without a match nearly half the time.

The general lesson is that certainly is a much more expensive requirement than probably, and the price is usually a factor like this one. Where a guarantee is not actually needed, insisting on one costs a great deal — which is the same trade Monte Carlo methods make deliberately, accepting an answer that is probably right in exchange for an answer at all.