Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-05T23:29:38.333Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimization results for a generalized coupon collector problem

Part of: Markov processes Combinatorial probability

Published online by Cambridge University Press:  21 June 2016

Emmanuelle Anceaume ,
Yann Busnel ,
Ernst Schulte-Geers  and
Bruno Sericola
Emmanuelle Anceaume*
Affiliation:
CNRS
Yann Busnel*
Affiliation:
Ensai
Ernst Schulte-Geers*
Affiliation:
BSI
Bruno Sericola*
Affiliation:
Inria
*
* Postal address: CNRS, Campus de Beaulieu, 35042 Rennes Cedex, France.
** Postal address: Ensai, Campus de Ker-Lann, BP 37203, 35172 Bruz Cedex, France.
*** Postal address: BSI, Godesberger Allee 185-189, 53175 Bonn, Germany.
**** Postal address: Inria, Campus de Beaulieu, 35042 Rennes Cedex, France. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we study a generalized coupon collector problem, which consists of analyzing the time needed to collect a given number of distinct coupons that are drawn from a set of coupons with an arbitrary probability distribution. We suppose that a special coupon called the null coupon can be drawn but never belongs to any collection. In this context, we prove that the almost uniform distribution, for which all the nonnull coupons have the same drawing probability, is the distribution which stochastically minimizes the time needed to collect a fixed number of distinct coupons. Moreover, we show that in a given closed subset of probability distributions, the distribution with all its entries, but one, equal to the smallest possible value is the one which stochastically maximizes the time needed to collect a fixed number of distinct coupons.

Keywords

Coupon collector problemoptimizationSchur-convex functions

MSC classification

Primary: 60C05: Combinatorial probability
Secondary: 60J05: Discrete-time Markov processes on general state spaces
Type
Short Communications
Information
Journal of Applied Probability , Volume 53 , Issue 2 , June 2016 , pp. 622 - 629
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.)

References

[1]Anceaume, E., Busnel, Y. and Sericola, B. (2015).New results on a generalized coupon collector problem using Markov chains.J. Appl. Prob. 52, 405–418.CrossRefGoogle Scholar
[2]Anceaume, E., Busnel, Y., Rivetti, N. and Sericola, B. (2015).Identifying global icebergs in distributed streams. In Proc. of the 34th IEEE Int. Symposium on Reliable Distributed Systems (SRDS'15), Montréal, Québec, Canada.Google Scholar
[3]Boneh, A. and Hofri, M. (1997).The coupon-collector problem revisited—a survey of engineering problems and computational methods.Commun. Statist. Stoch. Models 13, 39–66.Google Scholar
[4]Doumas, A. V. and Papanicolaou, V. G. (2013).Asymptotics of the rising moments for the coupon collector's problem.Electron. J. Prob. 18, 1–15.CrossRefGoogle Scholar
[5]Flajolet, P., Gardy, D. and Thimonier, L. (1992).Birthday paradox, coupon collectors, caching algorithms and self-organizing search.Discrete Appl. Math. 39, 207–229.CrossRefGoogle Scholar
[6]Marshall, A. W., Olkin, I. and Arnold, B. C. (2011).Inequalities: Theory of Majorization and Its Applications, 2nd edn.Springer, New York.CrossRefGoogle Scholar
[7]Rubin, H. and Zidek, J. (1965).A waiting time distribution arising from the coupon collector's problem. Tech. Rep. 107, Department of Statistics, Stanford University.Google Scholar