Minimum samples needed to identify labeled coupon mappings
The Minimum Number of Samples in the Labeled Coupon Collector Problem
Discrete Mathematics
Summary
The coupon collector problem is about collecting all types of coupons, but this paper studies a tougher version where the connection between coupons and labels is unknown and must be figured out from samples. The authors find the least number of samples required to completely identify which coupon has which label in two different cases: when the label set is known and when it isn’t. They also show how to build the minimal sample collections needed. Additionally, the paper looks at partial identification, determining the minimum samples needed to identify some of the coupons.
What this means in practice
- •For network protocol designers: Define minimal packet collection strategies to deduce unknown network node labels with limited observations.
- •For data deduplication engineers: Optimize sampling to reliably identify duplicate records when labels or identifiers are partially unknown.
A theory result. No direct application yet.
Authors
Andrew Tan, Daniella Bar-Lev, Ryan Gabrys, Zohar Yakhini, Paul H. Siegel
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.