◄ WORLD V · SONNY 5DART 544 · a helldive at the table

THE BIRTHDAY COLLISION 23 people, even odds

Why hash tables collide sooner than you expect: with m slots you get a 50% collision after only about 1.2√m insertions, not m/2. The classic case: 23 people share a birthday with probability just over ½. Here i-13 multiplies the no-collision odds the product (m−i)/m for 23 in 365 and gets P(collision) = 0.5073.

THE TECHNIQUE P(collision) = 1 − the product (m−i)/m

The demo multiplies the survival odds for 23 people in 365 days: live demo

HISTORY & CREDIT birthday paradox · von Mises 1939

“You need 183 people (half of 365).” — the count grows like √m, not m: 23 is enough for even odds; 70 gives 99.9%. cited

the product · the product of (m−i)/m is the chance all differ.
the √m · ~1.2√m items for 50% — the birthday bound haunts hashing and cryptography.
1939 · posed by Richard von Mises; a staple of collision analysis.

Collisions come at √m, not m. probability

RECOMMEND FOR I-13 the odds, on the compiler

On i-13, the product for 23 in 365 gives P(collision) just over 0.5:

$ i13 run hs_birthday.i13 RUN OK · 482 step(s) · call depth 24 p_no = 0.49270276567601445 p_coll = 0.5072972343239855 over_half = 1

Recommend as a NULL — a theorem (B39). The birthday bound is an exact probability identity, computed here to the digit; a fact the collision cost obeys, not an invariant a mechanism enacts. NULL — 23 people, even odds.