The Labeled Coupon Collector Problem with Random Sample Sizes and Partial Recovery

2025/02/05 by Berrebi, Shoham Shimon, Yaakobi, Eitan, Yakhini, Zohar +1
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2502.02968

Abstract

We extend the Coupon Collector's Problem (CCP) and present a novel generalized model, referred as the k-LCCP problem, where one is interested in recovering a bipartite graph with a perfect matching, which represents the coupons and their matching labels. We show two extra-extensions to this variation: the heterogeneous sample size case (K-LCCP) and the partly recovering case.

Related

• The Labeled Coupon Collector Problem
• On Conjectures concerning the Labeled Coupon Collector Problem
• Contributions to the Generalized Coupon Collector and LRU Problems
• The logarithmic Zipf version of the coupon collector's problem
• New results on a generalized coupon collector problem using Markov chains