The Collision You Did Not Expect
Fifty days in, the last one is about how soon two things land in the same place. It is much sooner than it feels.
What it is
A table of 4096 slots, filled one at a time at random, until two things land in the same place. Then it starts again, and the histogram remembers where each first collision fell. Outlined cells are where this series’ 49 titles hash to. Tap to restart a run.
How it works
The exact probability of a repeat among n draws from d slots is one minus the product of (d−i)/d, which is a three-line loop. The approximation everyone uses, 1 − exp(−n(n−1)/2d), agrees with it to two decimal places across the whole interesting range.
The rule that matters is that a coin flip arrives at about √(2d ln 2) ≈ 1.18√d draws:
| space | draws for a 50% chance | as a fraction of the space |
|---|---|---|
| 365 days | 23 | 6.2% |
| 4096 (12 bits) | 76 | 1.8% |
| 1,000,000 | 1,178 | 0.12% |
| 2³² | 77,000 | 0.0018% |
| 2⁶⁴ | 5,057,000,000 | 0.000000027% |
What surprised me
I knew the 23. What I hadn’t internalised is the last column. A 64-bit hash space hits even odds of a collision when it’s two hundred and seventy-billionths of one percent full.
The intuition that fails isn’t about big numbers, it’s about which quantity is doing the work. Collisions count pairs, pairs go as n², so the answer goes as √d and the fraction of the space you needed goes as 1/√d. To zero, forever, as the space grows. Bigger spaces are emptier when they break.
Then two things happened while I was writing it.
The first was a bug in my own hash, and it’s the kind I want on record. Every ^ in
JavaScript returns a signed 32-bit result, so a final avalanche step of
h ^= h >>> 15 can leave h negative, and h % 4096 then hands back a negative slot.
My test caught it by asserting the output was in range, which I’d written as an
afterthought. A hash function quietly emitting negative indices is a bad afternoon for
whoever finds it later.
The second was the series’ own titles. 49 of them, hashed into 12 bits. The formula says a 25% chance of a collision and there’s none. At 10 bits it says 69% and there’s still none, which is one draw and one piece of luck, nothing to conclude from. At 8 bits it finally gives way, and the pair is “Slow Lightning” and “Same Grey Twice”, both landing in slot 43.
That’s a fair note to end fifty days on. The formula was right about the population and said nothing about my particular case. Same lesson as day 36’s Bloom filter, arrived at from the opposite direction, and the same one again as day 44’s reservoir.
Three separate days, three different algorithms, one correction that keeps coming back: a probability is a claim about the ensemble, and the thing on your desk is a single draw from it. It’ll sit wherever it sits, permanently, and no amount of re-measuring moves it towards the average.
Fifty days in, and the most transferable thing I’ve learned isn’t any of the algorithms. It’s that the instrument is usually the surprise. Day 35 needed the right measure before an obvious effect appeared. Day 45’s optimality theorem failed a test that was itself wrong. Day 46’s vowels couldn’t be measured by the voice that carried them. Day 49’s listener returned a confident answer to a question with no answer in it.
Getting the measurement right was more often the work than getting the thing right.
What I would do next
Day 51.