Collect coupons by decomposing waiting stages

Try

A synthetic packet contains exactly one of four labels, A, B, C or D. Each packet is independent, and each label has probability 1/4 on every draw. Open packets until you have all four labels. Repeats count toward the number opened. The sequence A, C, A, C, B, B, D finishes in seven draws, but another sequence might take much longer.

Mark the draws that increase the number of distinct labels: draws 1, 2, 5 and 7. The waiting stages have lengths 1, 1, 3 and 2. They add to the total seven. A stage ends at its successful new label; its waiting time includes that successful draw.

Predict

Which stage should take longest on average? With three labels already collected, only one label can finish the collection. Its chance on each new draw is 1/4. At the first stage every label is new, so success is certain. Treating all four stages as having probability 1/4 would overestimate the early waits.

Predict whether the expected time should be four packets, sixteen packets, or something between. We will obtain 1+4/3+2+4=25/3, approximately 8.333 packets. An average need not be an integer, even though every actual completion time is an integer. Nor does this average promise completion by draw 9.

Experiment

Write a sequence of labels, underline each first appearance and divide the sequence into stages. For the supplied sequence A, C, A, C, B, B, D, verify the four stage lengths before changing the sequence to A, A, B, C, C, C, D. The new lengths are 1, 2, 1 and 3: the same total can be distributed differently across stages.

Next do a complete small enumeration rather than inventing random data. With two equally likely labels, list all eight strings of length three. Only AAA and BBB fail to contain both labels. Therefore completion by draw 3 has probability 6/8=3/4. The expected completion time will also equal 3, yet a quarter of trials are still incomplete at that deadline. An expectation and a completion probability answer different questions.

Use the distribution explorer with Number of labels N = 2 and Number of draws t = 3. Predict complete collection probability 3/4 from your enumeration, then reveal it. Change t to 2 and explain why completion probability falls to 1/2. Finally set N=1 and t=0, then t=1: completion changes from impossible to certain. These calculations use a deterministic recurrence, not newly sampled trials. The collision outputs answer a separate question and need not equal the collection probability.

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?

Number of labels N123456812 Number of draws t012345678910111213141516243264128256

Reveal occupancy probabilitiesReset occupancy experiment

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.

Understand

First justify the waiting-time formula. Let G be the number of independent trials through the first success, with constant success probability p satisfying 0<p≤1. For a positive integer M, the number min(G,M) equals the sum of the indicators of G>0, G>1, …, G>M−1. If G=3, exactly the first three of these indicators are one, provided M≥3. Taking expectations and increasing M gives the tail-sum formula E[G]=Σ from t=0 to infinity P(G>t). The limiting step is justified by monotone convergence of nonnegative quantities, not by rearranging terms with mixed signs.

The event G>t means the first t trials all fail. Independence gives probability (1−p)^t, so its geometric series sums to E[G]=1/p. The t=0 term is one because no trials have occurred. When p=1, G=1 deterministically and every later tail term is zero.

Now take a positive integer N of equally likely labels. Let Wₖ count draws from the moment k distinct labels have appeared through the next new label, for k=0,…,N−1. Conditional on any history reaching that stage, the unseen set has N−k members and future draws remain iid uniform. Until the stage succeeds that set is unchanged. Thus Wₖ has success probability (N−k)/N and mean N/(N−k). This reasoning is about future draws after the actual history, not merely the initial draw.

Path by path, the completion time T equals W₀+…+W_(N−1). Therefore linearity of expectation gives

E[T] = N(1/N + 1/(N−1) + … + 1) = N H_N.

Linearity does not require a proof that the stage durations are independent. Independent sampling was used to establish the geometric waits; it should not be confused with an extra independence requirement for adding their means. Each stage with positive success probability ends almost surely, so the finitely many stages and their finite expectations are well defined.

For a deadline, let Aᵢ be the event that label i is absent after t draws, where t is a nonnegative integer. Collection has failed exactly when at least one Aᵢ occurs. Each has probability (1−1/N)^t. The union bound gives

P(T>t) ≤ N(1−1/N)^t ≤ N exp(−t/N).

The last inequality follows from 1−u≤exp(−u). Missing-label events need not be independent for the union bound. For N=1, handle the empty-draw boundary directly: T=1, so survival probability is one at t=0 and zero for integer t≥1. In the product formula the zero-draw probability always means one, without asking a calculator to interpret 0⁰. A bound above one can simply be replaced by one.

For deeper finite checking, define qₜ(k) as the probability of k distinct labels after t draws. Initially q₀(0)=1. For 0≤k≤N,

q_(t+1)(k) = (k/N)qₜ(k) + ((N−k+1)/N)qₜ(k−1),

with entries outside 0,…,N set to zero. The first contribution repeats an already seen label; the second arrives from k−1 by a new label. The complete state remains complete. Thus qₜ(N)=P(T≤t), giving an exact finite recurrence for a small case. This is optional distributional depth, not an assumption needed for the expectation proof.

Apply

For four labels, use the exponential bound to guarantee failure probability at most 0.05. Solve 4exp(−t/4)≤0.05, obtaining t≥4ln80, approximately 17.5281. Thus t=18 is sufficient. It is not claimed to be the smallest qualifying deadline: the union bound and exponential replacement can both lose precision. Check that the expected time 25/3 is a different number for a different reason.

Now change the sampling mechanism. For two labels with probabilities 1/3 and 2/3, the first draw takes one packet. If it is the first label, the remaining mean wait is 3/2; if it is the second, the remaining mean wait is 3. Conditioning gives E[T]=1+(1/3)(3/2)+(2/3)3=7/2. Merely knowing “one label collected” no longer specifies the success probability; its identity matters.

If every label has positive probability, a general missing-label bound is Σᵢ(1−pᵢ)^t, which is at most N exp(−p_min t), with p_min the smallest label probability. It tends to zero and has a summable geometric tail, proving almost-sure completion and finite expectation. If a required label has probability zero, completion is impossible almost surely. Changing the sampling assumptions requires changing the calculation, not just substituting a new N.

Continue

Use the written tasks to derive a remaining-stage expectation, compute a small completion distribution and distinguish conservative deadline certificates from actual minima. Return to geometric trial mechanisms for the waiting-time convention, or to harmonic sum bounds to estimate N H_N for large N. Neither an average nor a successful finite experiment supplies a guaranteed deadline; state the probability and the assumptions alongside any operational recommendation.