How many trials does it take to collect all different types of a population with probability p ?

摘要

Coupons are collected one at a time (independently andwith replacement) from a population containing N distinct types.This process is repeated until all N different types (coupons)have been collected (at least once). Recently, interesting results have beenpublished regarding the asymptotics of the moments and the variance, of thenumber TN of coupons that a collector has to buy in order to find all Nexisting different coupons as N--- 00. Moreover, the limitdistribution of the random variable TN (appropriately normalized), hasbeen obtained for a large class of coupon probabilities (see, [9], [10], and[11]). This classical problem of probability theory has found a plethora of applicationsin many areas of science, and quite recently, it has been highly involved withcryptography. In this note we take advantage of the above results and presentin detailed various examples that illustrate problems similar to those onefaces in the real life. We also conjecture on the minimum of the variance V [TN].