A Waiting Time Distribution Arising from the Coupon Collector's Problem

摘要

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)