Optimization Results for a Generalized Coupon Collector Problem

Abstract : We study in this paper a generalized coupon collector problem, which consists in 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 non-null 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.
Type de document :
Article dans une revue
Journal of Applied Probability, Applied Probability Trust, 2016, 53 (2)
Liste complète des métadonnées

https://hal.inria.fr/hal-01397403
Contributeur : Bruno Sericola <>
Soumis le : lundi 19 décembre 2016 - 10:54:09
Dernière modification le : mardi 16 janvier 2018 - 15:54:19
Document(s) archivé(s) le : mardi 21 mars 2017 - 07:56:00

Fichier

final_HAL.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01397403, version 1

Citation

Emmanuelle Anceaume, Yann Busnel, Ernst Schulte-Geers, Bruno Sericola. Optimization Results for a Generalized Coupon Collector Problem. Journal of Applied Probability, Applied Probability Trust, 2016, 53 (2). 〈hal-01397403〉

Partager

Métriques

Consultations de la notice

768

Téléchargements de fichiers

28