





















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 $\binom{n}{s}$ 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\le s\le 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 Keywords: Coupon Collector's Problem, Group Drawings, Uniform Distribution, Expected Collection Time, Schilling's Conjecture, Optimal Distribution.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。