skip to content

Why does a random identifier space of n values tolerate only about sqrt(n) identifiers before a collision is likely?

level: seniorimportance: should knowfreq 62%

answer

  1. collisions belong to pairs
  2. k identifiers, about k^2/2 pairs
  3. each pair matches with chance 1/n
  4. risk crosses one near sqrt(2n)
  5. in bits: half the width

basics

~20 s

Because collisions happen between pairs, and k identifiers make about k^2/2 pairs, each colliding with probability 1/n. The summed risk reaches order 1 near k = sqrt(2n), so the tolerable count grows only as the square root of the space.

solid answer

~40 s

Count the bad events properly: a collision is a property of a **pair**, so `k` identifiers give `k(k-1)/2` chances to collide, not `k`. Each pair of uniform draws from a space of `n` values matches with probability `1/n`, so the union bound gives `P(any collision) <= k^2 / (2n)`. That expression crosses order 1 when `k` is around `sqrt(2n)` - the square root of the space, not some fraction of it. In bits this is brutal and memorable: a `b`-bit random identifier is comfortable only up to roughly `2^(b/2)` draws, so identifier width buys collision headroom at half rate. Every extra bit of width adds half a bit of usable exponent.

code

pseudocode · 7 lines
pseudocode
// upper bound on the chance that k random ids from a space of n values collide
function collision_bound(k, n):
    pairs = k * (k - 1) / 2     // one bad event per unordered pair
    risk  = pairs / n           // union bound: each pair matches with chance 1/n
    if risk >= 1:
        return 1                // past this point the bound is vacuous
    return risk

go deeper

for a junior

Recall the shape of the rule: the number of random identifiers you can mint safely is roughly the square root of the size of the space they are drawn from, not a large fraction of it.

for a middle

Explain where the square root comes from - k identifiers create about k^2/2 pairs, each matching with probability 1/n - and convert the result into bits, where it means half the identifier width.

for a senior

Demonstrate that you check the assumption as well as the arithmetic: truncated columns, coarse seeds and non-uniform generators all shrink the effective space, and each makes the real risk worse than the rule suggests.

for a principal

Own the width decision end to end. Weigh the storage and index cost of wider identifiers against the consequence of a duplicate, and be explicit that the rule bounds likelihood, never possibility.

## The bad events are pairs, not identifiers The instinct that a space of `n` values is fine until you have used a decent fraction of `n` is the error this question exists to correct. A collision is not a property of one identifier; it is a property of **two**. So the right set of bad events to enumerate is the set of unordered pairs: ``` number of pairs = k * (k - 1) / 2 ~ k^2 / 2 ``` The pair count grows **quadratically** in `k` while the space stays fixed, and that mismatch is the whole phenomenon. ## From the pair count to the square root For two identifiers drawn uniformly and independently from `n` values, the probability that they are equal is `1/n` - fix the first, and the second must land on that one value out of `n`. Summing that probability over all pairs gives the union bound: ``` P(at least one collision) <= (k * (k - 1) / 2) * (1 / n) ~ k^2 / (2n) ``` Solving for a target risk `p` gives `k <= sqrt(2 * n * p)`. Two consequences fall straight out: 1. The tolerable count scales as **sqrt(n)**. Quadrupling the space only doubles the safe count. 2. The target risk `p` sits **inside a square root**, so demanding a risk a million times smaller costs only a factor of a thousand in capacity. Safety is cheap once you are on the right side of the square root, and impossible once you are on the wrong side. ## What the rule costs in bits With a `b`-bit identifier the space is `n = 2^b` and the safe count is about `2^(b/2)`: | Width | Space size | Roughly safe count | |---|---|---| | 64 bits | 2^64 | 2^32, about 4.3 billion | | 96 bits | 2^96 | 2^48, about 2.8 * 10^14 | | 128 bits | 2^128 | 2^64, about 1.8 * 10^19 | So widening an identifier from 96 to 128 bits - 32 extra bits - buys 16 bits of collision headroom, a factor of `2^16` more identifiers, not `2^32`. Reading the table the other way is the useful design habit: name the number of identifiers the service will ever mint, square it, and check that the space comfortably exceeds it. If you want an explicit risk rather than "order 1", put it in: keeping the risk under one in a billion in a 128-bit space allows `sqrt(2 * 2^128 * 10^-9)`, about `8 * 10^14` identifiers - still an enormous number, which is why the width is chosen as it is. ## Why this is a ceiling on risk, not a promise of safety Two separate cautions belong in the answer. - **The bound is an upper limit.** `k^2 / (2n)` over-states the true collision probability, because it sums over pairs that overlap. That direction is the safe one: if the bound clears your budget, you are done. - **Its assumption is the fragile part.** Every term used `1/n`, which presumes each identifier is drawn uniformly and independently from the full space. Real generators break this in ways the mathematics cannot see: - a seed derived from a coarse clock, so machines starting together draw the same first values; - a generator whose output is not uniform over the full width, silently shrinking `n`; - **truncation**, the most common of all - keeping the low 64 bits of a 128-bit identifier to fit a column moves you from `2^64` safe draws to `2^32`, a factor of four billion, in one schema decision. Under any of these the real risk is *worse* than the square-root rule says, so the rule is a limit on how safe you could possibly be rather than a guarantee. ## Saying it well in an interview - Lead with the pair count: `k` identifiers, `k^2/2` chances to collide. - Multiply by the per-pair chance `1/n` and read off `k ~ sqrt(n)`. - Convert to bits out loud: half the width, as an exponent. - Name truncation and weak seeding as the ways the estimate becomes optimistic. - Be clear that the result says when collisions become *likely*, not when they become possible - two draws can collide on the second identifier, and a system that cannot tolerate that at all needs coordination rather than a wider random draw.

  • Does adding 32 bits to an identifier buy 32 bits of collision headroom?
    No, it buys 16. The safe count is about `2^(b/2)`, so each extra bit of width adds half a bit of usable exponent. Going from 96 to 128 bits moves the comfortable count from roughly `2^48` to roughly `2^64` - a factor of `2^16`, not `2^32`.
  • A schema stores only the low 64 bits of a 128-bit identifier; what happens to the estimate?
    The space in the formula is whatever is actually stored, so `n` drops from `2^128` to `2^64` and the safe count falls from about `2^64` to about `2^32`. Truncating for a narrower column is the single most common way a correctly sized identifier becomes an under-sized one.
  • The generator reuses a coarse seed on restart, so draws are not uniform - how does that affect the bound?
    It invalidates the per-pair probability. Every term assumed a pair matches with chance exactly `1/n`; a biased or repeated seed makes matches more likely than that, so the true risk exceeds the estimate. The square-root rule describes the best case for a well-behaved generator, never a floor under a bad one.

saying these in an interview costs you the question

  • Thinks collisions only begin once the space is nearly exhausted
  • Assumes doubling the bit width doubles the safe count
  • Counts identifiers rather than pairs of identifiers
  • Trusts the square-root rule under a biased generator
  • Believes a collision is impossible below the square-root point