How many people need to be in a room before two of them probably share a birthday? Most people guess around 180. The answer is 23. Fill the room and watch the matches turn up.
Press "Add people until a match" a few times and note where it stops. Then run 1,000 rooms: the amber line lands on the white curve.
Each dot is a person, placed on a ring of 365 days at their birthday. Birthdays are random and equally likely; February 29 is left out. When two people share a day, both dots turn amber.
The white curve is the exact chance that at least one pair matches: P = 1 − 365! / ((365 − n)! · 365n). It passes 50.7% at 23 people and 99.9% at 70. The amber line is the share of simulated rooms that had a match at each size.
We picture ourselves in the room: what are the odds someone shares my birthday? With 23 people that is only 1 − (364/365)22 ≈ 5.9%. You would need 253 other people to reach even odds.
But the question is about any pair at all, and pairs grow with the square of the room. Each pair matches with chance 1/365, so the chance of no match is roughly e−pairs/365, which drops below one half once there are about 253 pairs.
Replace 365 days with any number of possible labels, and collisions show up after roughly the square root of that number. Engineers plan around this, and attackers exploit it.
A hash with n-bit outputs takes about 2n tries to match one given value, but only about 2n/2 to find any two inputs that match. That halving is why 160-bit SHA-1 was retired. In 2017 Google and CWI Amsterdam published the first real SHA-1 collision: two different PDF files with the same hash.
In the demo: 23 is close to √365; collisions start near the square root.A version 4 UUID has 122 random bits, so 5.3 × 1036 possible values. The birthday rule says you would need to make about 2.7 × 1018 of them before the chance of any duplicate reaches 50%. That is why systems can create IDs independently without checking with each other.
In the demo: the pairs estimate 1 − e−pairs/N with N = 2122.A hash table drops keys into numbered slots. Even a table with plenty of free space will see two keys land in the same slot surprisingly early, so every practical design includes a plan for collisions, such as chaining entries in a list or probing for the next free slot.
In the demo: 365 slots, 23 keys, a coin-flip chance of a collision.Git names every commit by a long hash, but people use the first 7 hex characters. That gives 268 million values, and a project with tens of thousands of commits will contain clashing short IDs. Git now lengthens its abbreviations automatically as a repository grows; the Linux kernel uses 12 characters.
In the demo: a bigger room needs a bigger calendar to stay match-free.A partial DNA profile might match a random person with odds of one in many millions. But comparing every profile in a database to every other one means billions of pairs, so some partial matches between unrelated people are expected. Searches of state databases in the US found such pairs and forced courts to weigh the difference between the two questions.
In the demo: "matches me" (5.9%) versus "any pair matches" (50.7%).In September 2009 the Bulgarian lottery drew the same six numbers in two draws four days apart, prompting an investigation. With thousands of lotteries holding draws for decades, some draw somewhere repeating an earlier one is far more likely than any particular repeat.
In the demo: each new draw is another person entering a very large room.