Birthday Paradox

The birthday paradox is the surprising fact that in a group of just 23 people, there's a greater than 50% chance that two share a birthday. Setup: $n$ people, each with a uniformly random birthday from 365 days. What's the probability that at least two share a birthday? The complement trick: $$P(\text{collision}) = 1 - P(\text{all different}) = 1 - \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdots \frac{365-n+1}{365}$$ Approximation: Using $1 - x \approx e^{-x}$ for small $x$: $$P(\text{all different}) \approx e^{-n(n-1)/(2 \cdot 365)}$$ Setting this to $1\mathrm{/}2$$\frac{1}{2}$ and solving: $n \approx \sqrt{2 \cdot 365 \cdot \ln 2} \approx 22.5$, confirming $n = 23$. General rule: In a space of $N$ equally likely values, expect a collision after about $\sqrt{\pi N / 2} \approx 1.177\sqrt{N}$ samples. Concrete example: A hash function outputs 32-bit values ($N = 2^{32} \approx 4.3 \times 10^9$). After just $\sqrt{\pi \cdot 2^{32} / 2} \approx 82{,}138$ random hashes, there's a 50% collision probability. This is why 32-bit hashes are dangerously short. Intuition: People compare the number of people (23) to the number of days (365) and think collisions are rare. But the number of pairs is $\binom{23}{2} = 253$, and each pair has a $\frac{1}{365}$ collision chance. With 253 independent "shots," a hit becomes likely. When to use: Estimating collision probabilities in hashing, cryptography, sampling, and randomized algorithms. Any time you're drawing from a large space and wondering "how many draws until a repeat?"