Home > Research > Publications & Outputs > The generalized coupon collector problem
View graph of relations

The generalized coupon collector problem

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published

Standard

The generalized coupon collector problem. / Neal, Peter John.
In: Journal of Applied Probability, Vol. 45, No. 3, 09.2008, p. 621-629.

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Harvard

Neal, PJ 2008, 'The generalized coupon collector problem', Journal of Applied Probability, vol. 45, no. 3, pp. 621-629. <http://projecteuclid.org/euclid.jap/1222441818>

APA

Vancouver

Neal PJ. The generalized coupon collector problem. Journal of Applied Probability. 2008 Sept;45(3):621-629.

Author

Neal, Peter John. / The generalized coupon collector problem. In: Journal of Applied Probability. 2008 ; Vol. 45, No. 3. pp. 621-629.

Bibtex

@article{4eaff2a4746843a8b9b977628feadcee,
title = "The generalized coupon collector problem",
abstract = "Coupons are collected one at a time from a population containing n distinct types of coupon. The process is repeated until all n coupons have been collected and the total number of draws, Y, from the population is recorded. It is assumed that the draws from the population are independent and identically distributed (draws with replacement) according to a probability distribution X with the probability that a type-i coupon is drawn being P(X = i). The special case where each type of coupon is equally likely to be drawn from the population is the classic coupon collector problem. We consider the asymptotic distribution Y (appropriately normalized) as the number of coupons n → ∞ under general assumptions upon the asymptotic distribution of X. The results are proved by studying the total number of coupons, W(t), not collected in t draws from the population and noting that P(Y ≤ t) = P(W(t) = 0). Two normalizations of Y are considered, the choice of normalization depending upon whether or not a suitable Poisson limit exists for W(t). Finally, extensions to the K-coupon collector problem and the birthday problem are given. ",
author = "Neal, {Peter John}",
year = "2008",
month = sep,
language = "English",
volume = "45",
pages = "621--629",
journal = "Journal of Applied Probability",
issn = "0021-9002",
publisher = "University of Sheffield",
number = "3",

}

RIS

TY - JOUR

T1 - The generalized coupon collector problem

AU - Neal, Peter John

PY - 2008/9

Y1 - 2008/9

N2 - Coupons are collected one at a time from a population containing n distinct types of coupon. The process is repeated until all n coupons have been collected and the total number of draws, Y, from the population is recorded. It is assumed that the draws from the population are independent and identically distributed (draws with replacement) according to a probability distribution X with the probability that a type-i coupon is drawn being P(X = i). The special case where each type of coupon is equally likely to be drawn from the population is the classic coupon collector problem. We consider the asymptotic distribution Y (appropriately normalized) as the number of coupons n → ∞ under general assumptions upon the asymptotic distribution of X. The results are proved by studying the total number of coupons, W(t), not collected in t draws from the population and noting that P(Y ≤ t) = P(W(t) = 0). Two normalizations of Y are considered, the choice of normalization depending upon whether or not a suitable Poisson limit exists for W(t). Finally, extensions to the K-coupon collector problem and the birthday problem are given.

AB - Coupons are collected one at a time from a population containing n distinct types of coupon. The process is repeated until all n coupons have been collected and the total number of draws, Y, from the population is recorded. It is assumed that the draws from the population are independent and identically distributed (draws with replacement) according to a probability distribution X with the probability that a type-i coupon is drawn being P(X = i). The special case where each type of coupon is equally likely to be drawn from the population is the classic coupon collector problem. We consider the asymptotic distribution Y (appropriately normalized) as the number of coupons n → ∞ under general assumptions upon the asymptotic distribution of X. The results are proved by studying the total number of coupons, W(t), not collected in t draws from the population and noting that P(Y ≤ t) = P(W(t) = 0). Two normalizations of Y are considered, the choice of normalization depending upon whether or not a suitable Poisson limit exists for W(t). Finally, extensions to the K-coupon collector problem and the birthday problem are given.

M3 - Journal article

VL - 45

SP - 621

EP - 629

JO - Journal of Applied Probability

JF - Journal of Applied Probability

SN - 0021-9002

IS - 3

ER -