The idea: 23 people are enough for a coin flip
How many people must be in a room before two of them probably share a birthday? Most people guess about 180, half of 365. The answer is 23: a room of 23 has a 50.7% chance of a shared birthday, and a room of 57 has 99%. Nothing is wrong with the maths; our intuition counts the wrong thing. This surprise is called the birthday paradox (or birthday problem).
On the canvas, the calendar has one cell per day: blue means one person has that birthday, red means two or more (a shared birthday, with the count written in the cell). The chart plots the chance of a match against the number of people n; the squares at the bottom right are simulated rooms.
Count pairs, not people
When you walk into a room of 22 people you can match only 22 of them, so your own chance is small (about 6%). But the question is about any two people. A room of n people has n(n − 1)/2 pairs: 23 people make 253 pairs. Each pair shares a birthday with chance 1/365, so on average 253/365 = 0.69 pairs match. The number of pairs grows like n², which is why the chance climbs so fast. (Demo 1: people walk in until two share a birthday: with seed 22 the first match comes with person 23, exactly the median.)
The exact chance: multiply the "no match" chances
It is easier to count the opposite, that all birthdays are different. Person 1 can have any day. Person 2 must miss person 1: 364/365. Person 3 must miss both: 363/365. Person n must miss n − 1 days:
For n = 23 the product is 0.4927, so P(shared) = 0.5073. (Demo 2: why 23? count the pairs.)
| people n | pairs n(n − 1)/2 | P(shared), exact | approx 1 − e−n(n−1)/730 |
|---|---|---|---|
| 10 | 45 | 11.7% | 11.6% |
| 20 | 190 | 41.1% | 40.6% |
| 23 | 253 | 50.7% | 50.0% |
| 30 | 435 | 70.6% | 69.6% |
| 40 | 780 | 89.1% | 88.2% |
| 57 | 1 596 | 99.0% | 98.7% |
| 70 | 2 415 | 99.9% | 99.9% |
The approximation comes from 1 − x ≈ e−x for small x: the product becomes e−(0 + 1 + … + (n−1))/365 = e−n(n−1)/(2·365). Each of the n(n − 1)/2 pairs "fails to match" with chance about e−1/365, as if the pairs were independent.
Check it by simulation
A formula is easy to doubt, so run the experiment. Run 100 rooms draws 100 rooms of n people from a seeded random generator and colours each room red if any two people in it share a day. The share of red rooms is an orange dot on the chart. With 1 000 rooms of 23 people the share lands within a few percent of 50.7%, and the error shrinks like 1/√(rooms), as in Monte Carlo estimation of π. (Demo 3: 1 000 rooms of 23 people; Demo 4: simulate the whole curve puts dots at n = 10, 20, 23, 30, 40, 57.)
The √N rule and hash collisions
Nothing here is special to 365. Put n items into N equally likely slots and the chance of no collision is about e−n²/(2N). It drops to 1/2 when
So a collision becomes likely after about √N items, not N/2. This is the rule behind hash tables, random IDs and the birthday attack on cryptographic hashes.
| values | N | 50% collision after | what it means |
|---|---|---|---|
| birthdays | 365 | 23 | the room on the canvas |
| 4-digit PIN | 10 000 | 119 | two of 119 random PINs probably match |
| 32-bit hash | 232 ≈ 4.3·109 | 77 164 | a 32-bit checksum is not a unique ID |
| 64-bit hash | 264 ≈ 1.8·1019 | 5.1·109 | a birthday attack is within reach |
| 128-bit hash / UUID | 2128 ≈ 3.4·1038 | 2.2·1019 | safe for IDs; 264 work to find a hash collision |
An n-bit hash therefore gives only n/2 bits of collision resistance: finding any two inputs with the same digest takes about 2n/2 tries, while finding an input for a given digest (a preimage) takes 2n. That is why MD5 (128 bits) is too short for signatures and modern digests such as SHA-256 have 256 bits. (Demo 5: hash collisions and the √N rule.) Hash tables live with collisions on purpose: see open hashing (separate chaining), closed hashing (linear probing) and Java's HashMap. A Bloom filter turns collisions into its false-positive rate, and encryption vs hashing covers what a hash is for.
Not to be confused with the pigeonhole principle
The pigeonhole principle says 366 people guarantee a shared birthday. The birthday paradox is about probability: a match is already likely far below that bound. Counting with permutations and combinations gives the same product: P(all different) = P(365, n) / 365n.
What the page leaves out
Real birthdays are not uniform (more in September, fewer on holidays), which makes a match slightly more likely, and 29 February is ignored. The page also leaves out the "three people share a day" version (88 people for 50%), the chance that someone shares your birthday (253 people for 50%), the generalized birthday attack on several lists, and Pollard's rho, which finds collisions with almost no memory.