Daniel Berend

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 (Formula presented.) coupons is drawn from a total of (Formula presented.) distinct coupons. While the classical CCP (with single-coupon draws) is well understood, the group-draw variant, where packages of size (Formula presented.) 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 (Formula presented.) packages of size (Formula presented.). Schilling showed that, for (Formula presented.), the uniform distribution yields the minimal expected time for collecting all coupons. She further conjectured that, for (Formula presented.), 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.