On Conjectures concerning the Labeled Coupon Collector Problem

2025/10/27 by Barak-Pelleg, Dina, Berend, Daniel
#68W20 #Combinatorics (math.CO) #FOS: Mathematics #Primary: 60C05 #Probability (math.PR) #Secondary: 05C80

paper · doi:10.48550/arxiv.2510.23249

Abstract

We study a labeled variant of the classical Coupon Collector Problem (CCP), recently introduced by Tan et al., where coupons arrive in groups and only the set of labels is revealed. The goal is to determine the expected number of group drawings required to uniquely identify the labeling of all coupons. We focus on the case where groups consist of pairs (k=2), and provide rigorous proofs for two conjectures posed by Tan et al.

Citations

• On a Conjecture of Schilling Regarding the Coupon Collector's Problem
• Birthday paradox, coupon collectors, caching algorithms and self-organizing search

Related

• The Labeled Coupon Collector Problem
• On a Conjecture of Schilling Regarding the Coupon Collector's Problem
• The Labeled Coupon Collector Problem with Random Sample Sizes and Partial Recovery
• Approaching the coupon collector's problem with group drawings via Stein's method
• Some new aspects of the coupon-collector's problem