Abstract
This paper surveys the coupon collector’s waiting time problem with random sample sizes and equally likely balls. Consider an urn containing m red balls. For each draw, a random number of balls are removed from the urn. The group of removed balls is painted white and returned to the urn. Several approaches to addressing this problem are discussed, including a Markov chain approach to compute the distribution and expected value of the number of draws required for the urn to contain j white balls given that it currently contains i white balls. As a special case, E[N], the expected number of draws until all the balls are white given that all are currently red is also obtained.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
I. Adler and S. M. Ross, “The coupon subset collection problem,” Journal of Applied Probability vol. 38 pp. 737–746, 2001.
R. Bosch, “Optimal card-collecting strategies for magic: The gathering,” The College Mathematics Journal vol. 31(1) pp. 15–21, 2000.
W. Feller, An Introduction to Probability Theory and Its Application, Wiley: New York, Third Edition, 1970.
L. Holst, “On birthday, collectors’, occupancy and other classical urn problems,” International Statistical Review vol. 54(1) pp. 15–27, 1986.
L. Holst, “Extreme value distributions for random coupon collector and birthday problems,” Extremes vol. 4(2) pp. 129–145, 2001.
T. Huillet and S. Martinez, “Sampling from finite random partitions,” Methodology and Computing in Applied Probability vol. 5(4) pp. 467–492, 2003.
G. Ivchenko, “How many samples does it take to see all the balls in an urn?” Mathematical >Notes vol. 64(1) pp. 49–54, 1998.
C. Klaassen, “Dixie cups – sampling with replacement from a finite population,” Journal of Applied Probability vol. 31(4) pp. 940–948, 1994.
X. Li and L. Ni, “A pipeline architecture for computing cumulative hypergeometric distributions. Proceedings of the 7th Symposium on Computer Arithmetic, Urbana, IL, 4–6 June, 166–72, 1985.
R. Ling and J. Pratt, “The accuracy of peizer approximations to the hypergeometric distribution, comparisons to other approximations. Journal of the American Statistical Association vol. 79 pp. 49–60, 1984.
A. Myers and H. Wilf, “Some new aspects of the coupon collector’s problem,” SIAM Journal of Discrete Mathematics vol. 17(1) pp. 1–17, 2003.
D. Newman and L. Shepp, “The Dixie cup problem,” American Mathematical Monthly vol. 67 pp. 58–61, 1960.
G. Polya, “Eine wahrscheinlichkeitsaufgabe zur kunderwerbung,” Zeitschrift fur Angewandte Mathematika und Mechanik, vol. 10(1–3) pp. 96–97, 1930.
S. Ross, Introduction to Probability Models, Harcourt: Burlington, MA, Seventh Edition, pp. 200–202, 2000.
T. M. Sellke, “How many IID samples does it take to see all the balls in box?” Annals of Applied Probability vol. 5(1) pp. 294–309, 1995.
D. Smith, “Decision making and card collecting,” IMA Journal of Management Mathematics vol. 16 pp. 89–97, 2005.
W. Stadje, “The collector’s problem with group drawings,” Advances in Applied Probability vol. 22 pp. 866–882, 1990.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kobza, J.E., Jacobson, S.H. & Vaughan, D.E. A Survey of the Coupon Collector’s Problem with Random Sample Sizes. Methodol Comput Appl Probab 9, 573–584 (2007). https://doi.org/10.1007/s11009-006-9013-3
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11009-006-9013-3