Our starting point is the coupon collector's problem. 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 equiprobable 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 $\Theta(\max\{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.
2020 Mathematics Subject Classification. Primary 60C05; Secondary 00A72.