Coupon Collector
Completing a set of coupons from cereal boxes can take many draws because the same coupon may appear repeatedly. The coupon collector's problem models this process with different coupons, each equally likely on every independent draw [Wikipedia].
As the collection grows, a draw is less likely to find a new coupon.
How many draws are needed on average to collect all coupons?
We count every draw with tick 1, including one that finds a new coupon.
The Programβ
The variable x counts how many coupons are still missing.
A draw finds a new coupon with probability x / N, so we use flip(x / N) to decide whether this happens.
We only record whether the coupon is new, without choosing a coupon number.
The inner loop draws until it finds a coupon not yet in the collection.
The outer loop repeats this until the collection is complete, decreasing x after each new coupon.
We verify that the expected number of draws is at most , where is the -th harmonic number, written harmonic(N) in the source.
Verified@ert
coproc coupon_collector(N: UInt) -> ()
pre !?(N > 0)
pre N * harmonic(N)
post 0
{
var x: UInt = N
// The expected number of remaining draws is at most N * harmonic(x).
// The condition x <= N keeps x / N within [0,1].
@invariant(!?(x <= N) β N * harmonic(x))
while x > 0 {
var found_new: Bool = false
// The expected wait for the next new coupon is N / x draws.
// The expected number of later draws is at most N * harmonic(x - 1).
@invariant(ite(found_new, 0, N / x) + N * harmonic(x - 1))
while !found_new {
tick 1
found_new = flip(x / N)
}
x = x - 1
}
}
Verificationβ
The clause pre !?(N > 0) restricts the claim to positive N, and pre N * harmonic(N) supplies the bound.
The two highlighted @invariant annotations bound the draws still needed at the outer and inner loops.
We first check the inner loop, whose bound is then used to verify the outer loop.
Finding One New Couponβ
The inner loop waits for a new coupon using this invariant:
@invariant(ite(found_new, 0, N / x) + N * harmonic(x - 1))
For , a draw finds a new coupon with probability . We bound the expected number of draws until this happens by . One draw costs one tick, and with probability we must keep drawing:
The inner invariant adds for the coupons still missing after we find the next new one.
Once found_new is true, ite(found_new, 0, N / x) removes the waiting cost, so only the bound for later coupons remains.
Collecting the Remaining Couponsβ
The outer loop collects the remaining coupons using this invariant:
@invariant(!?(x <= N) β N * harmonic(x))
The term N * harmonic(x) bounds the draws needed for all x missing coupons.
The condition x <= N ensures that flip(x / N) uses a valid probability.
For , the term N * harmonic(x) combines the bounds for the next new coupon and all later coupons:
After the inner loop finds a new coupon, the expected number of remaining draws is at most .
Updating x to x - 1 makes this the outer invariant for the new value of x.
- Initialization:
x == Ngives the specified bound. - Exit: at
x == 0,harmonic(0) == 0gives the zero bound required bypost 0.
Explicit Uniform Drawsβ
We replace flip(x / N) with a sampler that draws uniformly from 1 through N.
Labels 1 through x represent the missing coupons, so found_new = coupon <= x records whether the draw is new.
The surrounding collection loops are unchanged, so the excerpt shows only one draw and its sampling loop.
Verified tick 1
// Draw an index uniformly from 1 through N.
var coupon: UInt = N
var chosen: Bool = false
@invariant(
!?(1 <= coupon && coupon <= N)
β (
ite(chosen, [coupon > x],
ite(coupon > x, (coupon - x) / coupon, 0)
) * (N / x)
+ N * harmonic(x - 1)
)
)
while !chosen && coupon > 1 {
chosen = flip(1 / coupon)
if !chosen {
coupon = coupon - 1
} else {}
}
// Labels 1 through x represent the currently missing coupons.
found_new = coupon <= x
Starting at coupon = N, the sampler accepts each candidate with probability 1 / coupon and otherwise tries the next smaller index, with 1 as the fallback.
For each index , reaching it has probability , so selecting it has probability .
Its internal flips add no ticks, so the same bound still counts coupon draws.
The term N / x bounds the further draws needed after a duplicate, while N * harmonic(x - 1) covers the draws after the next new coupon.
Before selection, is the fraction of remaining indices that are duplicates.
After selection, [coupon > x] records whether the drawn index is a duplicate.
At coupon = N, adding the preceding tick gives , recovering the waiting cost.
At sampler exit, assigning found_new = coupon <= x recovers the invariant for finding the next new coupon.
Earlier Versionβ
An earlier version uses a specification for uniform sampling and a separate summation lemma. The sampling loop above proves the same bound without that lemma or explicit sums.
See Alsoβ
- Geometric Loop bounds the expected number of tails before the first heads.
- One-Sided Random Walks distinguishes almost-sure termination from a finite expected number of iterations.
- Bounded Retransmission Protocol uses nested retry loops to bound delivery probabilities and costs.
Referencesβ
-
Wikipedia. Coupon collector's problem.
Introduces the problem and derives the expected total by summing the expected numbers of draws between new coupons.
-
Kaminski et al. (2016). Weakest Precondition Reasoning for Expected Run-Times of Probabilistic Programs.
-
Kaminski et al. (2018). Weakest Precondition Reasoning for Expected Runtimes of Randomized Algorithms.
Both papers analyze coupon collection with a cost model that also charges for assignments and guard evaluations.
(Section 9.1) -
SchrΓΆer et al. (2023). A Deductive Verification Infrastructure for Probabilistic Programs. OOPSLA.
The paper presents the coupon collector as a HeyVL case study.
(Example 1.2 and Figure 3)