Hostname: page-component-77c78cf97d-9dm9z Total loading time: 0 Render date: 2026-04-29T08:25:41.466Z 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
Get access Rights & Permissions [Opens in a new window]

Abstract

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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

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