The Hypergeometric Coupon Collection Problem and its Dual

Document Type : Research Paper


Epstein Department of Industrial and Systems Engineering , University of Southern California, Los Angeles, CA, USA


Suppose an urn contains M balls, of different types, which are removed from the urn in a uniform random manner. In the hypergeometric coupon collection problem, we are interested in the set of balls that have been removed at the moment when at least one ball of each type has been removed. In its dual, we are interested in the set of removed balls at the first moment that this set contains all of the balls of at least one type.


Main Subjects

[1] Adler I., Oren S., Ross S. M. (2003), The coupon collector’s problem revisited; Journal of Applied
Probability, 40; 513-518.
[2] El-Neweihi E., Proschan F., Sethuraman J. (1978), A simple model with applications in structural
reliability, extinction of species, inventory depletion and urn sampling; Advances in Applied Probability,
10(1); 232-254.
[3] Ross S. M. (2002), Probability models for computer science, Academic Press.
[4] Ross S. M., Shahshahani, M., Weiss G. (1980), On the number of component failures in systems whose
component lives are exchangeable, Mathematics of Operations Research, 5(3); 358-365