Birthday Paradox and Collision Bounds

Draw $k$ items uniformly from $n$ possibilities. The probability that some two coincide is

$1-{\prod }_{i=0}^{k-1}\left(1-\frac{i}{n}\right)\approx 1-e^{-k^2/(2n)}.$

A collision becomes likely once

$k\approx 1.18\sqrt{n}.$

The “paradox”: with $n=365$ days, only 23 people are needed for a 50% chance of a shared birthday, and 70 for 99.9%.

The $\sqrt{n}$ threshold — the useful form

$n$	$k$ for 50% collision	$k$ for 1% collision
365	23	3
$10^6$	1 178	142
$10^9+7$	37 000	4 500
$2^{32}$	77 000	9 300
$2^{61}-1$	$1.8\cdot 10^9$	$2\cdot 10^8$
$2^{64}$	$5.1\cdot 10^9$	$6\cdot 10^8$

Read this table before choosing a hash modulus. $10^9+7$ collides with probability near 1 once you hash $10^5$ distinct strings — which is why $2^{61}-1$ or double hashing is the right default. See Polynomial Hashing.

Where it appears

As a hazard

Situation	Consequence
String hashing with a small modulus	false equality
Hash tables	degraded performance
Random IDs / tokens	duplicates
Zobrist hashing with too few bits	wrong game analysis

As a tool

The same $\sqrt{n}$ threshold makes several algorithms work:

Algorithm	Uses the collision
Pollard’s rho	a random walk mod $p$ repeats after $O(\sqrt{p})$ steps → factorisation in $O(n^{1/4})$
Pollard’s kangaroo	two walks meet after $O(\sqrt{b-a})$ steps
Meet in the middle	$2^{n/2}$ from each half, matched by collision
Baby-step giant-step	$\sqrt{m}$ from each side
Cryptographic collision attacks	$2^{n/2}$ work to break an $n$-bit hash

Pollard’s rho is the cleanest example: the whole $O(n^{1/4})$ bound is the birthday paradox applied to a walk modulo an unknown prime factor.

Related expectations

Quantity	Value
First collision after	$\approx \sqrt{\pi n/2}\approx 1.25\sqrt{n}$ draws
All $n$ values seen	$n{H}_n\approx n\ln n$ draws
Expected distinct values after $k$ draws	$n\left(1-(1-\frac{1}{n}{)}^k\right)$
Expected collisions among $k$ draws	$\left(\genfrac{}{}{0ex}{}{k}{2}\right)/n$
$k$ for at least one specific value	$n$ draws expected

The contrast between $\sqrt{n}$ (some collision) and $n\ln n$ (all values seen) is worth internalising — they are the two ends of the same process and differ enormously.

The generalised birthday problem

For a collision among $j$ items rather than 2, the threshold is

$k\approx n^{(j-1)/j}.$

So a triple collision needs $n^{2/3}$ draws — much later than a pair. Wagner’s generalised birthday algorithm exploits this for $k$-sum problems.

Choosing hash parameters

Distinct items hashed	Minimum safe modulus
$10^3$	$10^9$
$10^5$	$10^{13}$
$10^6$	$10^{15}$
$10^6$, want $10^{-9}$ error	$\ge 10^{21}$ → $2^{61}-1$ or double hashing

Combined with a randomised base (against precomputed anti-tests), $2^{61}-1$ gives a collision probability of about $qn/2^{61}$ over $q$ comparisons — safely below $10^{-9}$ for any contest input.

The lower bound it implies

Because any algorithm distinguishing $n$ possibilities by random sampling needs $\Omega (\sqrt{n})$ samples to find a collision, the birthday bound is also a lower bound on generic attacks — which is why an $n$-bit cryptographic hash offers only $n/2$ bits of collision resistance.

See also: Polynomial Hashing · Pollard’s Rho · Probability