Balls and Bins and the Birthday Problem

A trading system assigns each incoming order a random 6-digit tag for logging. With a million possible tags, it feels safe to assume no two orders in a busy hour will ever collide. That intuition is wrong by a wide margin — the same wrongness that makes "what are the odds two people in this room share a birthday" surprise almost everyone. Balls-and-bins problems ask how many random placements it takes before some bucket gets more than one item, and the answer is always far smaller than "half the number of buckets."

An analogy: filling a hotel at random

Imagine a hotel with 365 rooms, and guests are assigned rooms uniformly at random, one at a time. You might guess you'd need over 180 guests (half the rooms) before two land in the same room. In reality it takes only about 23. Every new guest has to avoid a room already taken by any prior guest, and the number of "already taken" rooms grows with each arrival — the risk compounds combinatorially, not linearly, reaching 50% far faster than intuition expects.

The math, one piece at a time

Suppose there are $n$ bins and you throw $k$ balls, each landing independently and uniformly in one of the $n$ bins. Let $P(\text{no collision})$ be the probability that every ball lands in its own empty bin — no two share a bin. The first ball always finds an empty bin. The second must avoid the first ball's bin: probability $\frac{n-1}{n}$. The third must avoid two taken bins: probability $\frac{n-2}{n}$. Multiplying these survival probabilities together:

$$P(\text{no collision}) = \prod_{i=0}^{k-1} \frac{n-i}{n} = 1 \times \left(1-\frac{1}{n}\right) \times \left(1-\frac{2}{n}\right) \times \cdots \times \left(1-\frac{k-1}{n}\right) .$$

In words: each new ball's chance of dodging every bin already used shrinks a little, and the overall no-collision probability is the product of all those shrinking odds. Using the approximation $1-x \approx e^{-x}$ for small $x$, this product is approximately $e^{-k(k-1)/(2n)}$, so the collision probability is roughly

$$P(\text{collision}) \approx 1 - e^{-k^2/(2n)} .$$

Plain English: collisions become likely once $k$ grows to around $\sqrt{n}$, not around $n$ — the square root of the bin count, which is a dramatically smaller number than most people's gut estimate.

Worked example 1: the birthday problem itself

With $n = 365$ days and $k = 23$ people, $\frac{k^2}{2n} = \frac{529}{730} \approx 0.725$. So $P(\text{collision}) \approx 1 - e^{-0.725} \approx 1 - 0.484 = 0.516$ — just over 50%, matching the well-known result that 23 people gives roughly even odds of a shared birthday. Note that $\sqrt{365} \approx 19$, close to 23, confirming the square-root rule of thumb.

Worked example 2: order-tag collisions

Back to the logging system: $n = 1{,}000{,}000$ possible tags. How many orders $k$ before there's a 50% chance two share a tag? Setting $1 - e^{-k^2/(2n)} = 0.5$ gives $k^2/(2n) \approx 0.693$, so $k \approx \sqrt{1.386 \times 1{,}000{,}000} \approx 1{,}177$. Just over a thousand orders — likely inside a single busy minute — already gives a coin-flip chance of a duplicate, even though the tag space has a million values.

What this means in practice

Balls-and-bins reasoning shows up anywhere random IDs, hash keys, timestamps, or bucket assignments are used at scale: hash table collision rates, the odds two independently-generated trade IDs coincide, or how many random samples you can draw before two land in the same discretized price bucket in a backtest. The rule of thumb — collisions become likely once the count of items reaches roughly the square root of the number of bins — is worth memorizing precisely because it's so much smaller than intuition suggests.