Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-22T04:21:30.824Z Has data issue: false hasContentIssue false
  • English
  • Français

A Generalized Coupon Collector Problem

Part of: Stochastic processes Combinatorial probability

Published online by Cambridge University Press:  14 July 2016

Weiyu Xu  and
A. Kevin Tang
Weiyu Xu*
Affiliation:
Cornell University
A. Kevin Tang*
Affiliation:
Cornell University
*
∗ Postal address: School of Electrical and Computer Engineering, Cornell University, Ithaca, NY 14853, USA.
∗ Postal address: School of Electrical and Computer Engineering, Cornell University, Ithaca, NY 14853, USA.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

This paper presents an analysis of a generalized version of the coupon collector problem, in which the collector receives d coupons each run and chooses the least-collected coupon so far. In the asymptotic case when the number of coupons n goes to infinity, we show that, on average, (nlogn) / d + (n / d)(m − 1)log logn + O(mn) runs are needed to collect m sets of coupons. An exact algorithm is also developed for any finite case to compute the exact mean number of runs. Numerical examples are provided to verify our theoretical predictions.

Keywords

Coupon collector problemexpected runstate-space representationwireless communicationopportunistic scheduling

MSC classification

Secondary: 60G70: Extreme value theory; extremal processes 60C05: Combinatorial probability
Type
Research Papers
Information
Journal of Applied Probability , Volume 48 , Issue 4 , December 2011 , pp. 1081 - 1094
Copyright
Copyright © Applied Probability Trust 2011 

References

[1] Azar, Z., Broder, A. Z., Karlin, A. R. and Upfal, E. (1999). Balanced allocations. SIAM J. Comput. 29, 180–200.Google Scholar
[2] Feller, W. (1950). An Introduction to Probability Theory and Its Applications. John Wiley, New York.Google Scholar
[3] Foata, D. and Zeilberger, D. (2003). The collector's brotherhood problem using the Newman-Shepp symbolic method. Algebra Universalis 49, 387–395.Google Scholar
[4] Holst, L. (2001). Extreme value distributions for random coupon collector and birthday problems. Extremes 4, 129–145.Google Scholar
[5] Kan, N. D. (2005). Martingale approach to the coupon collection problem. J. Math. Sci. 127, 1737–1744.Google Scholar
[6] Mitzenmacher, M. D. (1996). The power of two choices in randomized load balancing. , University of California, Berkeley.Google Scholar
[7] Myers, A. N. and Wilf, H. S. (2003). Some new aspects of the coupon-collector's problem. SIAM J. Discrete Math. 17, 1–17.Google Scholar
[8] Neal, P. (2008). The generalised coupon collector problem. J. Appl. Prob. 45, 621–629.Google Scholar
[9] Newman, D. J. and Shepp, L. (1960). The double dixie cup problem. Amer. Math. Monthly 67, 58–61.Google Scholar
[10] Sharif, M. and Hassibi, B. (2006). Delay considerations for opportunistic scheduling in broadcast fading channels. IEEE Trans. Wireless Commun. 6, 3353–3363.Google Scholar