arXiv Open Access 2025

The Labeled Coupon Collector Problem

Andrew Tan Oriel Limor Daniella Bar-Lev Ryan Gabrys Zohar Yakhini +1 lainnya

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.DM cs.IT math.CO

Penulis (6)

Andrew Tan

Oriel Limor

Daniella Bar-Lev

Ryan Gabrys

Zohar Yakhini

Paul H. Siegel

Format Sitasi

APA MLA BibTeX

Tan, A., Limor, O., Bar-Lev, D., Gabrys, R., Yakhini, Z., Siegel, P.H. (2025). The Labeled Coupon Collector Problem. https://arxiv.org/abs/2507.15231

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2025
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓