Daniel Berend

Our starting point is the coupon collector's problem (CCP). In this problem, there are n coupons that are drawn uniformly randomly with replacement. The question is how many drawings on average are needed to collect at least one copy (or some other predetermined number m of copies) of each coupon? The problem may be traced back to the 18-th century, having been mentioned already by de Moivre. Numerous questions have been posed based on the problem since its inception, and it turned out to appear naturally in many applications. A naive simulation of the process is trivial to implement. However, the runtime of this algorithm makes it impractical for large values of n. We present here an alternative view of the coupon collecting process, for coupons with any probabilities, that allows us to increase the range of n-s (and m-s) for which the simulation may be run. For equi-probable coupons, we present additional improvements, making the simulation possible in a very short time practically for any n. More precisely, we show that the runtime of our algorithm is Θ(m+log⁡n). We present theoretical results concerning some of the quantities relevant to our algorithms and conduct simulations to test the algorithms in practice.