A WAITING TIME DISTRIBUTION ARISING FROM THE COUPON COLLECTOR'S PROBLEM.
Abstract
A certain waiting time distribution is considered which arises in the context of the Coupon Collector's Problem. In general, the term 'Coupon Collector's Problem' refers to the problem which confronts an individual who is attempting to collect a subset of some set of distinct items, by sampling with replacement, one item from this set on each of a sequence of independent trials, until this subset is obtained. The waiting time in question, denoted by S(r,N) (N = 1,2,...; r = 1,2,...,N), is the number of trials needed to obtain for the first time, r distinct elements from among N distinct elements, if each of the sequence of independent trials consists of sampling with replacement and equal probabilities, one element from among the N. The exact distribution of S(r,N) is obtained. Using this result an asymptotic approximation to this distribution is derived for the case r = N. Calculations illustrating the effectiveness of this approximation in the case N = 1000, are given. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 05, 1965
- Accession Number
- AD0620290
Entities
People
- Herman Rubin
- James Zidek
Organizations
- Stanford University