Count occupied buckets and collision risk under iid random assignment. Separate the chance of a collision from the expected number of colliding pairs.
Occupancy and birthday problem
An occupancy problem asks how objects are distributed among buckets: how many buckets are empty, how many are occupied, or how large a bucket's load becomes. The birthday problem asks for the probability that at least two objects share a bucket. For a quant developer, this gives a baseline for hash collisions in a data cache or random identifier scheme, before analysing how the system resolves those collisions.
The standard model assigns n labelled objects independently and uniformly to m labelled buckets. Each of the mn ordered assignments is equally likely. This is a mathematical model for the assignments, not evidence that a particular hash function, market identifier feed or trading-event stream behaves that way.
Four assignments, three different answers
Consider four distinct records assigned to ten buckets under that model. A collision means that two distinct records receive the same bucket; it does not mean that the records themselves are duplicates. A hash table must retain enough information to distinguish their keys.
Let K count occupied buckets and C count unordered pairs of records sharing a bucket. Then:
Question
Exact answer
Is there at least one collision?
P(C≥1)=0.496
How many colliding pairs on average?
E[C]=0.6 pairs
How many occupied buckets on average?
E[K]=3.439 buckets
Exact enumeration of four iid uniform assignments into ten buckets: one, two, three and four occupied buckets have probabilities 0.1%, 6.3%, 43.2% and 50.4%. Collision probability is 49.6%; mean colliding pairs is 0.6 and mean occupied buckets is 3.439.
Original exhaustive calculation over all 10,000 equally likely ordered assignments. The first three bars form the collision event; the three summaries measure different quantities.
The distinction matters because a run with a collision can contain several colliding pairs. Three records in one bucket already contribute (23)=3 pairs. A probability counts that run once; the pair count counts each pair.
Count the assignments with no collisions
For the first record, every bucket is available. Conditional on no earlier collision, the next records must avoid one, two and then three occupied buckets. Thus
Why “birthday”? Replace records with people and buckets with calendar dates. Under the simplified model of independent, uniform birthdays on 365 dates, 23 people give a collision probability of about 50.73%. This concerns any pair in the group, rather than everyone matching one chosen person's birthday. Actual birth dates need not be uniform, and the model excludes leap day.
Count pairs and occupied buckets with indicators
For each of the (2n) pairs, define an indicator function that equals one when its two assignments match. Each pair matches with probability 1/m. Summing their expected values gives
E[C]=m(2n).
For four records and ten buckets this is 6/10=0.6. It is not a 60% collision probability. Linearity of expectation does not require the pair indicators to be mutually independent; indeed, if two pairs among three records match, the third pair must match too.
For occupancy, use one indicator per bucket instead. A particular bucket stays empty if all n assignments miss it, with probability (1−1/m)n. Therefore
E[K]=m[1−(1−m1)n].
In our example, 10(1−0.94)=3.439. This is a mean across repeated assignments; an individual run has an integer number of occupied buckets. The empty-bucket indicator argument appears in Oliveira's notes, “Second question”.
The square-root scale is an approximation
Writing λ=n(n−1)/(2m), the usual birthday approximation is
P(C≥1)≈1−e−λ.
It follows by approximating log(1−r/m) with −r/m in the no-collision product. It is useful in the sparse regime; the sum of the omitted quadratic terms has order n3/m2, so small individual ratios alone do not describe the whole error. Around the birthday scale n proportional to m, this error shrinks as m grows. This explains why appreciable collision risk can arrive long before most buckets are occupied. Kleinberg, §1.1, bounds the approximation error.
For our small example, 1−e−0.6≈0.4512, against the exact 0.496: about 4.48 percentage points lower. Treating C as Poisson gives this same approximation, not an exact distribution. Here it is also a lower bound on collision probability because 1−x≤e−x bounds the no-collision product from above.
What changes when assignments are uneven?
If assignments remain independent and identically distributed, but bucket j has probability pj, then
E[C]=(2n)j=1∑mpj2,E[K]=j=1∑m[1−(1−pj)n].
These follow from the same indicator arguments. Unequal bucket probabilities increase the pair mean relative to uniform assignment, since ∑jpj2≥1/m. Neither mean by itself determines the probability of any collision. Dependence between assignments requires another model again: knowing the marginal bucket frequencies is insufficient.
Three distinct records are assigned independently and uniformly to four buckets. A colleague calculates (23)/4=0.75 and calls it the probability of a collision. What did they calculate, and what is the exact collision probability?
Answer. They calculated the expected number of colliding pairs: 0.75 pairs. The no-collision probability is (4⋅3⋅2)/43=3/8, so the exact collision probability is 5/8=62.5%. Runs in which all three records share a bucket contribute three pairs, which is why the mean pair count exceeds the probability of any collision.
