Birthday Collision Probability (Exponential Approximation)

Take $n$ values at random from a space of $N$. There are $\binom{n}{2} \approx n^2/2$ pairs among them, each pair matches with probability $1/N$, and if the pairs were independent the chance of no match at all would be $(1 - 1/N)^{n^2/2} \approx e^{-n^2/(2N)}$. Subtract from one and you have the page. The pairs are not quite independent, which is why this is an approximation rather than an identity — but the error is tiny wherever $n$ is small against $N$, and that is exactly where cryptography works.

The shape is the lesson: it is $n^2$ against $N$, not $n$ against $N$. Collisions therefore start appearing around the square root of the space, not around half of it. Twenty-three people out of 365 days is even money; fifty is 97%. Five billion random 64-bit values are even money in a space of eighteen quintillion. This is the birthday paradox, and it is only a paradox because people instinctively compare $n$ to $N$ when the arithmetic compares $n^2$ to $N$.

Why this page exists when the exact answer is one click away. The probability shard already carries the exact all-distinct product, $P = N!/((N-n)!\,N^n)$, which is the right tool whenever you can evaluate it — for 23 people and 365 days it gives 0.5073 against this page's 0.5155, so the approximation runs about 1.6% high. But the exact product is a product of $n$ factors, and cryptography routinely asks about $N = 2^{128}$ with $n$ around $2^{64}$. Eighteen quintillion multiplications is not a calculation anyone is going to perform, and the intermediate values underflow long before you finish. The exponential form collapses all of it into one exponential and stays accurate to many decimal places in exactly that regime. It is not a worse version of the exact answer; it is the version that exists at the sizes that matter. Use the exact product for small spaces, this one for large, and note that the approximation always errs on the pessimistic side — it never tells you a collision is less likely than it really is.

Where this gets used in practice, in rough order of how badly it bites. Random identifiers: a 64-bit random key is not safe as a unique identifier at internet scale, and a UUIDv4's 122 random bits are, comfortably. Nonces and IVs: a repeated nonce under AES-GCM is catastrophic rather than inconvenient — it leaks the XOR of two plaintexts and, worse, the authentication key — so the budget there is set at something like $2^{-32}$, not one half, and 96-bit random nonces are limited to around $2^{32}$ messages per key for exactly this reason. Hash collisions: this is where the halving of a digest's collision resistance comes from, and it has its own page. Shard keys and session tokens: a collision is usually a bug rather than a breach, but it is a bug that appears at a predictable scale and is far better predicted than discovered.

Choose the acceptable probability by consequence, not by habit. A one-in-a-million chance of a duplicated log identifier is nothing; a one-in-a-million chance of a repeated GCM nonce across a fleet is a decision you should be able to defend. And note how cheaply the requirement grows: halving the acceptable collision chance costs one bit of space, while doubling the number of values you intend to issue costs two.