Coupon collector’s problem variants with group drawings

Posted on by

Introduction

The coupon collector’s problem is an old standby in the puzzle community: what is the minimum number N of random selections with replacement from a set of s=1000 coupons that are needed to obtain at least one of every coupon in the set? This post collects solutions to some variants of this problem involving what Stadje [3] refers to as “group drawings,” where each random selection is not of a single coupon, but of a group of m=10 coupons. Python code implementing the formulas described here is available on GitHub.

Group drawing a subset (without replacement)

Results depend on how each group of coupons is selected. Stadje addresses the variant where at each turn we select a random subset of m distinct coupon types, i.e., sampling the m coupons without replacement (but always returning all coupons to the pile for the next turn).

In this case, the cumulative distribution function for N is

P(N \leq n)=\frac{1}{{s \choose m}^n}\sum\limits_{k=0}^{s} (-1)^k {s \choose k}{s-k \choose m}^n

with expected value

E(N)=-\sum\limits_{k=1}^{s} (-1)^k {s \choose k}\frac{1}{1-\frac{{s-k \choose m}}{{s \choose m}}}

Group drawing with replacement

Alternatively, we have considered here before the variant where at each turn we sample a group of m coupons with replacement, so that duplicates are possible within a group. In this case,

P(N \leq n)=\frac{1}{(s^m)^n}\sum\limits_{k=0}^{s} (-1)^k {s \choose k}(s-k)^{m n}

E(N)=-\sum\limits_{k=1}^{s} (-1)^k {s \choose k}\frac{1}{1-\frac{(s-k)^m}{s^m}}

Group drawing consecutively from a cycle

So far, nothing new. But this post was motivated by an interesting variant of the problem posed recently by John D. Cook [1]: arrange the s coupons in a circle, and at each turn, randomly select an “interval” of m coupons that appear consecutively around the circle.

A comment on the linked blog post mentions a very elegant solution to the continuous version of this problem described in [2,4,5], where we ask for the number N of random arcs of fixed length needed to cover the circle. For reference, the resulting distribution of N in this continuous case is given by

P(N \leq n)=\sum\limits_{k=0}^{\lfloor 1/a \rfloor} (-1)^k {n \choose k}(1-k a)^{n-1}

E(N)=1+\sum\limits_{k=1}^{\lfloor 1/a \rfloor} (-1)^{k-1}\frac{(1-k a)^{k-1}}{(k a)^{k+1}}

where a is the length of each arc as a fraction of the circumference.

It is a delightfully challenging exercise to apply this same inclusion-exclusion approach, where we are prohibiting uncovered “gaps” between arcs, to this discrete “consecutive coupon” collector problem. The resulting probability distribution is

P(N \leq n)=\frac{1}{s^n}\sum\limits_{j=1}^{n} \frac{s}{j} \left( \sum\limits_{k=0}^{j-1} (-1)^k {j \choose k}(j-k)^n \right) \left( \sum\limits_{k=0}^{\lfloor (s-j)/m \rfloor} (-1)^k {j \choose k}{s-1-k m \choose j-1} \right)

where the first inner summation counts ways to select exactly j specified distinct intervals in n turns (i.e., the number of surjections from [n] to [j]), and the second inner summation is the discrete analog to the continuous case summation above, counting ways to “cover” the entire cycle of s coupons with j distinct intervals of m consecutive coupons.

Unfortunately, unlike the other variants where we can compute the expected number of turns as a finite sum, it’s not clear to me how to compute the expected value here other than lower bound approximations from the series E(N)=\sum_{n=0}^{\infty}1-P(N<=n).

References:

  1. Cook, John D., Consecutive coupon collector problem [HTML]
  2. Solomon, H., Covering a Circle Circumference and a Sphere Surface, Chapter 4 in Geometric Probability, Philadelphia, PA: SIAM, p. 75-96, 1978 [PDF]
  3. Stadje, Wolfgang, The Collector’s Problem with Group Drawings, Advances in Applied Probability, 22(4) December 1990, p. 866-882 [JSTOR]
  4. Stevens, W. L., Solution to a Geometrical Problem in Probability, Annals of Eugenics, 9(4) 1939, p. 315-320 [PDF]
  5. Weisstein, Eric W., Circle Covering by Arcs, from MathWorld–A Wolfram Web Resource [HTML]

1 thought on “Coupon collector’s problem variants with group drawings”

  1. In paragraph 4.7 of my recent introductory book A first Course in Probability fot Computer and Data Science, World Scientific Press, 2023 simple but accurate heuristics are discussed for a variety of coupon collector problems

    Reply ↓

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.