Hostname: page-component-7b7567c8c-tnzcf Total loading time: 0 Render date: 2026-11-14T20:07:47.794Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimality Results for Coupon Collection

Part of:Special processes

Published online by Cambridge University Press:  24 October 2016

Mark Brown and
Sheldon M. Ross
Mark Brown*
Affiliation:
Columbia University
Sheldon M. Ross*
Affiliation:
University of Southern California
*
* Postal address: Department of Statistics, Columbia University, New York, NY 10027, USA. Email address: mb2484@columbia.edu
** Postal address: Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, CA 90089, USA. Email address: smross@usc.edu
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.

We consider the coupon collection problem, where each coupon is one of the types 1,…,s with probabilities given by a vector 𝒑. For specified numbers r 1,…,r s , we are interested in finding 𝒑 that minimizes the expected time to obtain at least r i type-i coupons for all i=1,…,s. For example, for s=2, r 1=1, and r 2=r, we show that p 1=(logr−log(logr))∕r is close to optimal.

Keywords

Multinomial trialPoissonizationlikelihood ratio orderedincreasing failure rate

MSC classification

Primary:60K99: None of the above, but in this section

Information

Type
Research Papers
Information
Journal of Applied Probability , Volume 53 , Issue 3 , September 2016, pp. 930 - 937
Copyright
Copyright © Applied Probability Trust 2016 

References

[1] Alam, K. (1970).Monotonicity properties of the multinomial distribution.Ann. Math. Statist. 41,315–317.Google Scholar
[2] Barlow, R. and Proschan, F. (1975).Statistical Theory of Reliability and Life Testing: Probability Models .Holt Rhinehart and Winston,New York.Google Scholar
[3] Marshall, A. W. and Olkin, I. (1979).Inequalities: Theory of Majorization and Its Applications .Academic Press,New York.Google Scholar
[4] Olkin, I. (1972).Monotonicity properties of Dirichlet integrals with applications to the multinomial distribution and the analysis of variance.Biometrika 59,303–307.CrossRefGoogle Scholar
[5] Rinott, Y. (1973).Multivariate majorization and rearrangement inequalities with some applications to probability and statistics.Israel J. Math. 15,60–77.CrossRefGoogle Scholar
[6] Wong, C. K. and Yue, P. C. (1973).A majorization theorem for the number of distinct outcomes in N independent trials.Discrete Math. 6,391–398.Google Scholar