On a conjecture on uniform group drawings in the coupon collector problem

We address a conjecture of Schilling concerning the optimality of the uniform distribution in the generalized Coupon Collector’s Problem (CCP) where, in each round, a subset (package) of s coupons is drawn from a total of n distinct coupons. While the classical CCP (with single-coupon draws) is well understood, the group-draw variant, where packages of size s are drawn, presents new challenges and has applications in areas such as biological network models. Consider the set of all distributions over the collection of (ns) packages of size s. Schilling showed that, for s=n−1, the uniform distribution yields the minimal expected time for collecting all coupons. She further conjectured that, for 2≤s≤n−2, the uniform distribution does not yield the minimum. We prove Schilling’s conjecture in full by presenting “natural” non-uniform distributions yielding strictly lower expected collection times. Explicit formulas are provided for the expected number of rounds under these and related distributions.