The coupon collector problem is a classic puzzle in probability: if there are n different types of coupons and you draw them at random (with replacement), how many draws do you need before you have collected every type at least once? A natural extension asks how many draws you need to collect every type at least m times, meaning you complete m full collections. In 1961, Erdos and Renyi solved this for any fixed number of collections m, showing that the total number of draws follows a specific bell-shaped limiting distribution called the Gumbel distribution, centered around a predictable location. They then asked a harder question: what happens when m is not fixed but grows as n grows? For example, what if you want 100 collections when there are 1,000 coupon types, or a million collections when there are a billion types?
This paper gives a complete answer to that 60-year-old question. The authors show that no matter how fast m grows with n, you can always find explicit formulas for the center and the scale of the distribution of the completion time. Once you standardize the completion time using these formulas, the distribution again converges to the Gumbel distribution. This holds across all possible growth rates of m, covering a huge range of regimes from m growing very slowly to m growing nearly as fast as n itself. The authors also pin down the precise expected value of the completion time in each regime.
The technical engine behind the results is a new method inspired by a classical trick called Poissonization, where a discrete random process is approximated by a continuous one that is easier to analyze. The authors adapt and extend this approach into a general methodology for finding the limiting distribution of hitting times in discrete random processes, not just the coupon collector problem. This broader framework could be useful for analyzing many other problems in probability and combinatorics where you want to know when a random process first reaches some goal.