Motivation
How many independently generated identifiers can be used before a collision becomes likely? A tempting guess is that the number must be close to the size of the identifier space. In fact, a collision becomes substantial around the square root of that size because there are quadratically many pairs that could collide.
We derive the exact probability in the uniform model, a quick union bound, and a second-moment argument. We then examine nonuniform probabilities and a pairwise-independent construction that shows why the full independence assumption cannot be dropped casually.
Definitions and model
Let be an integer. Draw independent uniform values from a set of labels. A collision occurs if for some distinct indices. Let
be the number of colliding pairs. Three equal values contribute three pairs, not one. Set , with the usual convention that for .
Concept lensCombinatorial
Count by label instead of by pair
Let be the number of draws equal to label . Then , and there is no collision exactly when every . Each label contributes , so again. A label drawn three times contributes three pairs.
Theorems
Theorem 3.4.1
(Exact collision probability)
For , the probability of no collision is
For it is zero. The empty product is one.
Theorem 3.4.2
(Bounds and the square-root scale)
For every , the collision probability satisfies
In particular, for fixed and , the probability stays on a nontrivial constant scale as grows.
Proofs
Proof: expose draws in order
Proof
(Exact product and collision bounds)
Assume . Conditional on the first draws being distinct, they occupy exactly labels. The next draw avoids them with probability . Multiplying these conditional probabilities for gives the product formula. If , the pigeonhole principle forces a collision. For or , the formula gives probability one of no collision.
For each pair , the probability of equality is . The union bound over all pairs gives , capped by one. For the lower bound, use in the no-collision product:
For the no-collision probability is zero, so the same inequality is immediate. Taking complements gives the claimed lower bound.
When , the mean tends to . For large , we have and . The inequality for bounds the product from the other side:
Both bounds tend to , so the collision probability tends to , strictly between zero and one for fixed . In particular, small makes this limit small, while a large fixed makes it close to one. A fixed finite does not imply a limiting probability of exactly one.
Proof X-ray
Count possible pairs, not just occupied labels
Where each hypothesis is used: the product formula needs only that each new draw is independent of the earlier ones and uniform, through the conditional probability of avoiding the occupied labels. The union bound needs only that each pair collides with probability . The exponential lower bound applies to every factor and uses . The key move is to count the pairs rather than the draws: the number of pairs, not of draws, sets the scale, so has constant order exactly when has order . The limit argument needs and for the sharper logarithm estimate, and it closes because both sides tend to .
A second-moment proof
Proof
(Second-moment lower bound)
Write . Distinct pair indicators are pairwise independent under the fully independent uniform model. For disjoint pairs this is immediate. If two pairs share one index, for example and , both equal one exactly when , which has probability , the product of their marginal probabilities. Pairwise independence of these indicators does not assert that all of them are jointly independent.
Linearity gives . Since and distinct covariances vanish,
For , Cauchy–Schwarz applied to yields
Indeed, . If , the collision probability is zero and the lower bound is interpreted as zero. This second-moment bound is weaker than the product-based exponential bound here, but the method extends to settings in which an exact product is unavailable. Its proof uses the variance as well as the expectation.
Proof X-ray
What the variance step really assumes
The bound is Cauchy–Schwarz and needs no independence. Independence enters only in , which requires the indicators and to be uncorrelated. That is a statement about three draws, , and pairwise independent draws do not give it. In the affine example , and instead of .
Unequal label probabilities
Now suppose the draws remain independent and identically distributed but label has probability , where . Define and . A specified pair collides with probability , so and the union bound gives , capped by one.
Disjoint pair indicators remain independent. For two pairs sharing one index, the probability both collide is , so their covariance is . There are three unordered overlapping pair-of-pairs for each triple of indices. Consequently,
The second term need not vanish. In fact by Cauchy–Schwarz, because . Concentrated label probabilities increase the chance of repeated values and can make the uniform estimate misleading. The expectation alone still yields an upper bound, but an accurate lower bound generally needs additional dependence information.
From a bound to a sampling budget
Suppose the goal is to keep collision probability at most , where . A sufficient condition is , because then the union bound gives . This is a conservative guarantee: its failure does not prove that the actual probability exceeds . Conversely, if , the product bound gives , so a collision occurs with probability at least .
The distinction between necessary and sufficient conditions matters when choosing an identifier size. For instance, a system designed with the union-bound criterion has a defensible upper bound under independent uniform generation. It cannot claim that every smaller space necessarily violates the target without evaluating or bounding the exact product in the other direction. Also, the model counts generated identifiers, including repeated attempts; silently resetting the count after a collision changes the experiment.
There is a quantitative way to assess the approximation . For , integration or the power series for gives
If and , summing this inequality over the product factors yields
Here is an explicit bound on the additional magnitude of the logarithm. When is proportional to , tends to zero, justifying the limiting approximation. At much larger , or when the denominator is small, the bound can be too loose to be informative; the exact finite product remains valid.
Reading the nonuniform variance
Consider independent draws from two labels with probabilities and . Then and . The mean number of colliding pairs is , while the variance formula gives . The positive second term comes from pairs of collision tests sharing a draw.
This value can be checked without the general formula. All three draws agree with probability , producing ; otherwise exactly two agree, producing . Thus , and subtracting gives . Since there are only two labels, a collision occurs with certainty even though the count varies. The example separates the event probability from the number of equal pairs.
Worked examples
Worked example 3.4.3
(Two draws)
For two independent uniform draws, there is just one pair. The collision probability is exactly , and both the exact product and the union bound give that answer. With one label, , two draws collide with certainty.
Worked example 3.4.4
(A three-label space)
With and , no collision occurs with probability . The collision probability is . The expected number of colliding pairs is , which is not the collision probability: when all three draws agree, they contribute three pairs at once.
Worked example 3.4.5
(A nonuniform pair)
For two labels with probabilities and , two independent draws collide with probability . The uniform two-label probability is . The heavier label makes a match more likely.
Worked example 3.4.6
(A useful quick estimate)
If and , then . The bounds give . The lower value is approximately . The exact product gives a more precise answer if needed; neither bound should be presented as the exact probability.
Interpreting a concrete probability
For a uniform space of labels and independent draws, the exact product gives a collision probability of approximately . Here , and the exponential lower bound is approximately . The upper bound is valid but less tight. These numbers refer to any equal pair among the draws; they do not describe the chance that a specified draw matches a specified other one, which is only .
The model also differs from sampling without replacement. If we choose labels uniformly without replacement, no two chosen labels can coincide, so the collision probability is zero. Both schemes may give each individual draw a uniform marginal distribution, but their joint distributions are different. Independence is a statement about the joint experiment, not merely about the distribution of one draw.
In a real identifier system, uniformity may be only an approximation and different users or machines may share randomness. The exact formula is therefore a prediction conditional on the stated generation process. If a deterministic rule prevents repeats, or a generator reuses a seed, use an analysis of that rule instead. A large nominal identifier space alone is not enough to justify the independent-uniform calculation.
The term collision also depends on what is counted. This chapter tests exact equality of labels. A hash table may call two distinct keys a collision when they map to the same bucket; the same mathematics applies only if the resulting bucket values meet the model assumptions. Whether two original keys are equal is a separate question.
Independence cannot be weakened silently
Pairwise independence of the individual draws does not imply the exact product formula. Work in and sample independent uniform . Let , , and . Each pair of these variables is jointly uniform on : the corresponding linear map from has nonzero determinant. Thus the draws are pairwise independent and individually uniform.
If , all three values agree. If , they are all distinct. Hence their collision probability is . Under three fully independent uniform draws from three labels, it is . Both models give the same collision probability for each specified pair, but their joint behavior differs. The union bound remains valid from pairwise marginals; the product formula and the variance calculation above used stronger assumptions.
Counterexample mode
Pairwise independent draws need not be mutually independent
The affine construction has only nine equally likely pairs , while three fully independent ternary draws have 27 equally likely triples. Knowing two affine draws determines the third. Equal pairwise distributions therefore do not determine the probability of a union involving all three pairs.
Common mistakes
Common mistake
(Expected collisions are not the collision probability)
The expected number of colliding pairs is not generally the probability of at least one collision. They agree only in special cases, because one outcome can contain several colliding pairs. The union bound uses the expectation as an upper bound, not an equality.
Common mistake
(Multiplying pair probabilities as if independent)
A single collision probability should not be multiplied repeatedly as if all pair-collision events were independent. Even with independent draws, the three events , and have a joint logical constraint. The sequential no-collision product conditions on the entire earlier history instead.
Common mistake
(Using the uniform formula for biased identifiers)
Finally, using the uniform formula for heavily biased identifiers understates risk. The relevant pair probability is , and the collision process may also have correlations beyond those of independent draws. State the random-generation model before applying a numerical guarantee.
Summary
Uniform independent draws give an exact no-collision product and simple bounds governed by . The quadratic number of pairs explains the square-root scale. Pair indicators are pairwise independent in this model, giving a second-moment bound; their full joint independence is not needed and can fail; it fails when and . Nonuniform or merely pairwise-independent draws require separate analysis.
Exercises
Quick check
(Compute the collision probability for uniform draws from labels.)
There is only one pair of draws.
Solution · Answer
There is one pair, which agrees with probability .
Quick check
(For , , compute the exact no-collision probability and the expected number of colliding pairs.)
Multiply the conditional probabilities of avoiding earlier labels; count pairs for the expectation.
Solution · Answer
The product is . The expected number of colliding pairs is . Its complement is the collision probability, illustrating that the expectation and probability differ.
Quick check
(Two labels have probabilities and . Compute the probability that two independent draws agree.)
List the two ways in which the two draws can agree.
Solution · Answer
The two ways to agree have probabilities and , so the answer is .
Quick check
(In the affine ternary construction, explain why makes the three values distinct and determine the collision probability.)
Look at the differences between the three values.
Solution · Answer
In , multiplication by nonzero permutes the three values , so adding gives three distinct labels. A collision occurs exactly when , which has probability .