A synthetic labeling system assigns each arriving record one of five labels, independently and uniformly. This is a probability model, not a claim about an actual hash function. Read three labels in order. A collision means at least two positions have the same label; it does not mean that all three agree.
Write down one sequence with no collision, one with exactly one matching pair, and one with three matching pairs. For example, (0,2,4), (0,2,0), and (2,2,2) meet those descriptions. The last sequence has three matching pairs but only one occurrence of the event “there is a collision.” Distinguishing a random count from a yes/no event will prevent a common probability error.
Predict
There are 5³=125 ordered sequences. Predict how many avoid repetition. After the first label, does the second have five available collision-free choices or four? After two distinct labels, how many remain?
The counts are conditional on all previous labels being distinct. These are successive choice counts, not a claim that the no-repeat events are independent.
Thus the collision probability is 1−60/125=13/25. Independently check by enumerating all triples (a,b,c) with each coordinate from 0 through 4 and counting those satisfying a=b or a=c or b=c. There are 65. This finite check verifies this case; the general argument follows below.
Experiment
One drawing process, two different questions
Each draw independently chooses one of N equally likely labels, with replacement. Predict the chance of any repeated label and the chance of seeing all N labels after t draws. Can one be large while the other is zero?
No probabilities revealed. Predict before revealing.
Try N = 3 with t = 2, 3 and 4. Explain why complete collection is impossible at two draws, why its probability at three draws is 2/9, and why a collision is certain by four draws. This temporary experiment does not award mastery.
Choose five labels and three draws. Predict the collision probability, the expected number of matching pairs, and whether all five labels could have appeared. Reveal and compare. Then increase the draws to six: a repeat becomes certain, but complete collection need not be certain. Reset before making another prediction. Displayed numerical probabilities are approximate evaluations of the stated finite model.
Five labels, k draws
Probability of no collision
Probability of collision
Expected matching pairs
0
1
0
0
1
1
0
0
2
4/5
1/5
1/5
3
12/25
13/25
3/5
6
0
1
3
The last column may exceed 1 because it counts pairs. A probability cannot exceed 1. Record the model assumptions with your comparison; changing the number of labels alone does not test whether a real system follows this model.
Understand
Let N≥1 be an integer number of labels and k≥0 an integer number of iid uniform draws. Write q for the probability of no collision. For k≤N, counting ordered sequences gives
q = N(N−1)⋯(N−k+1)/Nᵏ = ∏ from j=0 to k−1 of (1−j/N).
At k=0 the empty product is 1; at k=1 it is also 1. If k>N, pigeonhole gives q=0 directly. Never continue the formula into negative factors and interpret them as probabilities.
For each unordered pair of positions, its matching indicator has expectation 1/N. Therefore the number X of matching pairs has mean λ=k(k−1)/(2N). Finite linearity needs no independence between these indicators. Since X≥1 on the collision event, its probability is at most min(1,λ). This is the union bound, not an equality in general.
For k≤N every product factor is positive. The inequality ln(1−x)≤−x for 0≤x<1 gives ln q≤−λ. Hence
1−exp(−λ) ≤ P(collision) ≤ min(1,λ).
A logarithmic approximation needs an error estimate. For 2≤k<N set ρ=(k−1)/N and
R = k(k−1)(2k−1) / [12N²(1−ρ)].
The identity −ln(1−x)−x = integral from 0 to x of t/(1−t) gives an error between 0 and x²/[2(1−ρ)] whenever 0≤x≤ρ. Sum this bound for x=j/N and use the square-sum formula. It proves
−λ−R ≤ ln q ≤ −λ, so exp(−R) ≤ q/exp(−λ) ≤ 1.
Subtracting the probability bounds from 1 gives a collision interval from 1−exp(−λ) to 1−exp(−λ−R). Intersect its upper endpoint with min(1,λ) if useful. This integral proof is a short optional analytic justification; the exact finite product requires only counting. When k is at most a fixed constant times √N and N increases, R tends to zero. Merely knowing k<N does not make R small. Mathematical bounds are exact statements; rounded decimal evaluations are not automatically outward-rounded certificates.
Uniformity and independence both matter. With independent nonuniform probabilities p₁,…,pₙ, the two-draw matching probability is Σpᵢ². With perfectly dependent draws all equal to one uniform initial label, every marginal is uniform but a repeat is certain after two draws. An arbitrary deterministic hash function supplies neither random assumption by itself.
Apply
Use N=10 labels. Compare k=4 and k=5, first with exact products, then with λ. Which is the first sample size with collision probability above one half? Explain why a monotonicity argument is needed to say “first.”
Check the changed case and its interpretation
At four draws q=(9/10)(8/10)(7/10)=0.504, so collision probability is 0.496. At five draws multiply by 6/10 to get q=0.3024 and collision probability 0.6976. Coupling all sample sizes to successive prefixes of one draw sequence shows that a collision cannot disappear as draws are added. Thus five is the first size above one half. The respective λ values are 0.6 and 1. The exponential lower bound at five is 1−exp(−1), above one half, but that sufficient certificate alone does not establish what happened at four.
Finally audit a proposed conclusion: “Twelve test keys did not collide, so the hash is injective.” Replace it with a statement limited to the checked keys. Explain what randomness assumptions would be needed for a probability statement about future keys.
The adjacent collection problem asks when every label has appeared. That is a different stopping time from the first repeated label. Preserve the same explicit sampling assumptions when comparing them; neither an expected waiting time nor a collision-free test is a universal deadline guarantee.
Apply · explain · revise
Practice and reasoning
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
Three independently sampled uniform labels take values in {0,1,2,3}. Count all ordered outcomes and the outcomes with no repeated label. Give the exact collision probability and independently describe an exhaustive enumeration that verifies it. Extend the formula to general N,k, explicitly handling k=0, k=1 and k>N.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
For k iid uniform labels in N bins let X count unordered pairs of draw positions having equal labels. Derive E[X]. In the N=4,k=3 case compare E[X] with the collision probability. For three draws and N>1 show that the three pair indicators are pairwise independent but not mutually independent.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
For N≥2 and 0≤k≤N put λ=k(k−1)/(2N). Prove 1−exp(−λ)≤P(collision)≤min(1,λ). Explain the domains and inequality directions. For N=50 determine the first k giving collision probability at least 1/2 using exact products: q(8)=0.5541618475008 and q(9)=0.465495951900672. Explain what the exponential bound alone certifies.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
For 2≤k<N define ρ=(k−1)/N, λ=k(k−1)/(2N), and R=k(k−1)(2k−1)/(12N²(1−ρ)). Prove −λ−R≤ln q≤−λ from the identity −ln(1−x)−x=∫ from 0 to x of t/(1−t) dt. Convert this to bounds for collision probability and for q/exp(−λ). Show that k=O(√N) as N→∞ makes the latter ratio tend to 1; explain why saying k<N alone does not justify a small error.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Two independent labels have probabilities (1/2,1/3,1/6). Find their collision probability and compare it with uniform sampling from three labels. Prove that Σp_i²≥1/N for any distribution on N labels. Then construct uniform marginal labels with certain collision and explain why the birthday product fails.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
A deterministic hash function maps arbitrary keys to N buckets. An engineer claims the birthday product applies to any k distinct keys and that a collision-free test proves the function has no collisions. Repair both claims. Under the ideal model in which the distinct tested keys receive independent uniform bucket values, derive an upper bound on the probability of at least one collision for k=12,N=256. Give a concrete deterministic counterexample and a conclusion that a collision-free observation actually supports.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
