The Labeled Coupon Collector Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916852978941952 |
|---|---|
| author | Tan, Andrew Limor, Oriel Bar-Lev, Daniella Gabrys, Ryan Yakhini, Zohar Siegel, Paul H. |
| author_facet | Tan, Andrew Limor, Oriel Bar-Lev, Daniella Gabrys, Ryan Yakhini, Zohar Siegel, Paul H. |
| contents | We generalize the well-known Coupon Collector Problem (CCP) in combinatorics. Our problem is to find the minimum and expected number of draws, with replacement, required to recover $n$ distinctly labeled coupons, with each draw consisting of a random subset of $k$ different coupons and a random ordering of their associated labels. We specify two variations of the problem, Type-I in which the set of labels is known at the start, and Type-II in which the set of labels is unknown at the start. We show that our problem can be viewed as an extension of the separating system problem introduced by Rényi and Katona, provide a full characterization of the minimum, and provide a numerical approach to finding the expectation using a Markov chain model, with special attention given to the case where two coupons are drawn at a time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_15231 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Labeled Coupon Collector Problem Tan, Andrew Limor, Oriel Bar-Lev, Daniella Gabrys, Ryan Yakhini, Zohar Siegel, Paul H. Discrete Mathematics Information Theory Combinatorics We generalize the well-known Coupon Collector Problem (CCP) in combinatorics. Our problem is to find the minimum and expected number of draws, with replacement, required to recover $n$ distinctly labeled coupons, with each draw consisting of a random subset of $k$ different coupons and a random ordering of their associated labels. We specify two variations of the problem, Type-I in which the set of labels is known at the start, and Type-II in which the set of labels is unknown at the start. We show that our problem can be viewed as an extension of the separating system problem introduced by Rényi and Katona, provide a full characterization of the minimum, and provide a numerical approach to finding the expectation using a Markov chain model, with special attention given to the case where two coupons are drawn at a time. |
| title | The Labeled Coupon Collector Problem |
| topic | Discrete Mathematics Information Theory Combinatorics |
| url | https://arxiv.org/abs/2507.15231 |