The Birthday Problem

Chapter 01The Bet You'd Lose

It's a Friday evening in 1939, and Richard von Mises is holding court at a dinner party in Istanbul. He's been exiled from Berlin for six years now — a Jewish mathematician fleeing the Nazis — and he's developed a party trick. He scans the room, counts heads, and announces: "I'll bet anyone here that at least two of us share a birthday."

There are 23 people at the table. The other guests do quick mental arithmetic. Twenty-three out of 365? That's barely 6%. Several take the bet. Von Mises goes around the table collecting birthdays. Person 11 and person 19 — both April 7th.1

Von Mises collects his winnings. He'll do this again and again over the years, winning more often than not. Not because he's lucky, but because the probability of a shared birthday among 23 people is 50.7%. A coin flip, slightly in his favor.

This is the birthday problem, and it has been annoying people who think they understand probability since 1939.

The birthday problem isn't hard because the math is complicated. The math, as we'll see, is almost absurdly straightforward. It's hard because your brain ships with a factory-installed bug in how it counts relationships between things. And that bug doesn't just cost you bar bets — it breaks cryptographic systems, corrupts DNA evidence, and quietly undermines any situation where you're searching for coincidences in a crowd.

Chapter 02The Wrong Question

Here's what happens in your head when you hear "23 people, 365 possible birthdays." You think: What are the odds someone shares MY birthday?

And you calculate, correctly, that each other person has a 1/365 chance of matching you. With 22 other people, the probability that at least one matches is roughly 22/365 ≈ 6%. Pathetic odds. No wonder you'd take that bet.

But that's the wrong question. Von Mises didn't bet that someone shares your birthday. He bet that any two people share any birthday. You were counting arrows pointing at you. He was counting arrows pointing at everyone.

This is where intuition breaks. We think about the problem linearly — 23 people, 23 chances. But pairs grow quadratically. Double the people and you don't double the pairs — you roughly quadruple them. Ten people give you 45 pairs. Twenty give you 190. Thirty give you 435.

Chapter 03The Exact Calculation

Here's the beautiful thing about the birthday problem: the math is a single elegant chain of multiplications. We just need to calculate the probability that nobody shares a birthday, then subtract from 1.

The first person walks in. They can have any birthday — 365 out of 365 are "safe."

The second person needs to avoid one birthday. The odds of no collision: 364/365.

The third person needs to avoid two birthdays: 363/365.

Keep going. The 23rd person needs to avoid 22 birthdays: 343/365.

So the probability of at least one match is 1 − 0.4927 = 0.5073. Just over 50%.2

Notice the shape of this calculation. Each new person only subtracts a tiny sliver of probability — 364/365 is 99.73%, barely a scratch. But you're multiplying these together, and multiplication is merciless. It's the same reason a chain of 99.7%-reliable components produces a fragile system. Each link is almost perfect. The chain is not.

The numbers are stark. At 23 people you cross 50%. By 50 people you're at 97%. By 70 people it's 99.9%. And at 100 people the probability of no match is about 0.00000003 — roughly the odds of flipping 25 heads in a row.3

Chapter 04The Birthday Party Simulator

Tables are convincing. Experiencing it yourself is better. The simulator below lets you build a party one guest at a time, watch birthdays land on a calendar, and see collisions happen far sooner than your gut expects. Then run 10,000 automated parties to build the full probability curve.

Chapter 05Hash Collisions and the Birthday Attack

In 1994, a French computer scientist named Antoine Joux realized that the birthday problem was more than a parlor puzzle. It was a weapon.4

Cryptographic hash functions take any input and produce a fixed-size "fingerprint" — say, a 128-bit number. There are 2¹²⁸ possible outputs, a number so large it makes 365 look quaint (it's about 340 undecillion). Surely you'd need to try an astronomical number of inputs before finding two that produce the same hash?

The birthday problem says no. You only need about √(2¹²⁸) ≈ 2⁶⁴ attempts. That's still a lot — about 18 quintillion — but it's the square root of what naive intuition suggests. For a 64-bit hash, the birthday bound drops to 2³² ≈ 4 billion, which a modern laptop can churn through in minutes.

The generalized birthday problem shows up everywhere in computer science. Database designers worry about it when choosing hash table sizes. Network engineers encounter it in packet deduplication. Git uses SHA-1 hashes to identify commits, and the birthday bound is why Google's 2017 SHA-1 collision attack (called "SHAttered") required "only" 2⁶³ computations rather than the 2¹⁶⁰ that brute force would demand.6

Chapter 06The DNA Database Problem

In 2001, an Arizona state employee named Kathryn Troyer was running routine checks on the state's DNA database when she found something unsettling. Two profiles matched at 9 out of 13 genetic loci. The FBI's standard calculation said such a match had a probability of roughly 1 in 754 million. It looked like the two samples had to be from the same person — or close relatives.7

They weren't. The two men were unrelated — one was Black, the other white. They'd never met. The "one in 754 million" match was, in fact, a birthday-problem collision hiding in a database of 65,000 profiles.

How? The Arizona database held about 65,000 profiles. The number of possible pairs: 65,000 × 64,999 / 2 ≈ 2.1 billion. When you run two billion lottery tickets against odds of one in 754 million, you expect to find matches. The surprise would be if you didn't.

This isn't hypothetical. The FBI's CODIS database now holds over 20 million profiles. Defense attorneys have increasingly demanded "database match" probability corrections. Some courts accept them; others don't. The math hasn't changed since von Mises's dinner party. Our legal system is still catching up.

Chapter 07The Von Mises Version: Your Birthday

There's a punchline that makes the birthday problem even more counterintuitive, and it comes from von Mises himself.

You need only 23 people for a 50% chance that some pair shares a birthday. But how many people do you need for a 50% chance that someone shares your specific birthday?

The answer: 253.9

Not 23. Not 50. Not even 183 (half of 365, which is most people's first guess). Two hundred and fifty-three. The same number as the pairs in a room of 23 — which is, of course, not a coincidence at all.

The math: each person has a 364/365 chance of not matching you. You need (364/365)ⁿ ≤ 0.5, which gives n ≥ 253. That's the linear version of the problem — you against the world, one pair at a time. The original birthday problem harnesses the quadratic explosion of all-against-all to compress 253 "effective" comparisons into just 23 people.

This factor of 11 is the birthday problem in a single number. It measures the gap between "one target" and "all targets" — between the linear and the quadratic. And it's exactly the gap that human intuition fails to bridge.

Chapter 08Why Your Brain Can't Count Pairs

The birthday problem is, at its heart, a story about combinatorial explosion and why humans can't feel it in their bones.

We evolved to track things, not relationships between things. You can glance at a crowd and estimate its size — evolution gave us that. But you can't glance at a crowd and estimate the number of handshakes. The number of entities grows linearly; the number of pairwise connections grows as the square. Our brains have no hardware for this.

This failure mode recurs constantly:

In project management, Brooks's Law says adding people to a late project makes it later — because communication channels between n people grow as n(n−1)/2. A team of 5 has 10 channels. A team of 15 has 105. The overhead quadruples when the headcount triples.10

In social networks, Metcalfe's Law says a network's value grows as the square of its users — because value comes from connections, not nodes. This is why social platforms exhibit winner-take-all dynamics.

In testing, if your software has 100 features that might interact pairwise, you have 4,950 potential interactions to test. Adding 10 more features doesn't add 10 tests — it adds 1,045 new pairs.

Von Mises knew this, which is why he kept making the bet. It wasn't about the money. It was about demonstrating that even smart people — mathematicians, physicists, the dinner-party elite of wartime Istanbul — carry a blind spot so fundamental that they'll bet real money on the wrong side of it.

The birthday problem is a calibration test for your intuition. And almost everyone fails it the first time. That's not a character flaw. It's a feature of the hardware. The fix is what it always is in mathematics: stop trusting the gut. Do the multiplication.