Skip to main content

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 Nβ‰₯1N\ge1 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 NN 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 Nβ‹…HNN\cdot H_N, where HN=βˆ‘j=1N1/jH_N=\sum_{j=1}^{N}1/j is the NN-th harmonic number, written harmonic(N) in the source.

Simplified sampling and loop invariants
Expected: 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 for finding a new coupon
@invariant(ite(found_new, 0, N / x) + N * harmonic(x - 1))

For 0<x≀N0<x\le N, a draw finds a new coupon with probability x/Nx/N. We bound the expected number of draws until this happens by N/xN/x. One draw costs one tick, and with probability 1βˆ’x/N1-x/N we must keep drawing:

1+(1βˆ’xN)β‹…Nx=Nx.1+\left(1-\frac{x}{N}\right)\cdot\frac{N}{x}=\frac{N}{x}.

The inner invariant adds Nβ‹…Hxβˆ’1N\cdot H_{x-1} 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 for collecting the remaining coupons
@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 x>0x>0, the term N * harmonic(x) combines the bounds for the next new coupon and all later coupons:

Nx+Nβ‹…Hxβˆ’1=Nβ‹…Hx.\frac{N}{x}+N\cdot H_{x-1}=N\cdot H_x.

After the inner loop finds a new coupon, the expected number of remaining draws is at most Nβ‹…Hxβˆ’1N\cdot H_{x-1}. Updating x to x - 1 makes this the outer invariant for the new value of x.

  • Initialization: x == N gives the specified bound.
  • Exit: at x == 0, harmonic(0) == 0 gives the zero bound required by post 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.

Explicit uniform sampling and its invariant
Expected: 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 jj, reaching it has probability j/Nj/N, so selecting it has probability (j/N)β‹…(1/j)=1/N(j/N)\cdot(1/j)=1/N. Its internal flips add no ticks, so the same Nβ‹…HNN\cdot H_N 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, max⁑(couponβˆ’x,0)/coupon\max(\mathtt{coupon}-x,0)/\mathtt{coupon} 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 1+(Nβˆ’x)/x=N/x1+(N-x)/x=N/x, 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​

References​