Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2509.17201 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913111666065408 |
|---|---|
| author | Berend, Daniel Sher, Tomer |
| author_facet | Berend, Daniel Sher, Tomer |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_17201 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On a Conjecture on Uniform Group Drawings in the Coupon Collector Problem Berend, Daniel Sher, Tomer Probability Combinatorics 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. |
| title | On a Conjecture on Uniform Group Drawings in the Coupon Collector Problem |
| topic | Probability Combinatorics |
| url | https://arxiv.org/abs/2509.17201 |