The Minimum Number of Samples in the Labeled Coupon Collector Problem

Abstract

The Labeled Coupon Collector Problem (LCCP) is an extension of the classical Coupon Collector Problem (CCP) in which one must deduce an unknown mapping between coupons and labels by collecting unordered subsets of k coupons and their associated labels, where deduction relies on analyzing the intersections and differences of the unordered subsets. In this work, we establish a fundamental connection between the LCCP and the combinatorial theory of separating systems. Using this framework, we completely characterize the minimum required number of samples to deduce all labels in two settings: Type-I, where the label set is known in advance, and Type-II, where it is unknown. We provide deterministic constructions of minimal separating and covering systems, yielding explicit bounds that are tighter than those found in existing literature. Furthermore, we extend our analysis to the partial recovery problem, characterizing the minimum number of samples required to identify a specified number of target coupons.

arXiv comment26 pages + 2 pages Bibliography + 3 pages Appendix, 4 figures, Submitted to SIAM Journal on Discrete Mathematics