xix. Birthday Problem

Problem. With $k$ people and $d=365$ equally likely birthdays, what is the probability that two share a birthday? 23 people already give more than $50\%$.

$\mathrm{Pr}[\text{collision}]=1-{\prod }_{i=0}^{k-1}\frac{d-i}{d}\approx 1-e^{-k(k-1)/(2d)}.$

double birthdayCollision(int k, int d) { double p = 1; for (int i = 0; i < k; i++) p *= (double)(d - i) / d; return 1 - p; }
int birthdayHalf(int d) { int k = 0; while (birthdayCollision(k, d) < 0.5) k++; return k; }

Consequence	Value
people for 50%	$\approx \sqrt{2d\ln 2}\approx 1.18\sqrt{d}$ (23 for 365)
random 64-bit hashes of $n$ strings	collision likely once $n\approx 2^{32}$
hashing mod a $10^9$ prime with $10^5$ items	collision probability $\approx 1-e^{-5}$: use two moduli or 64 bits (Hashing)
Pollard’s rho	finds a factor $p$ after $O(\sqrt{p})$ steps, by the same bound

Proof: the product formula and the approximation

The $i$-th person avoids the $i$ earlier birthdays with probability $\frac{d-i}{d}$, independently given the earlier ones being distinct, so all are distinct with probability ${\prod }_{i<k}\frac{d-i}{d}$. Using $1-x\le e^{-x}$, the product is at most $e^{-\sum i/d}=e^{-k(k-1)/(2d)}$, which is also the leading-order value; it drops below $\frac{1}{2}$ when $k(k-1)\ge 2d\ln 2$. The code finds $k=23$ for $d=365$.