Cutoff profile for the coupon collector with many collections

Source abstract

We solve the problem posed by Erdős and Rényi in $1961$ about the limiting distribution of the number of draws $T_{n,m}$ that a coupon collector needs to complete $m$ collections of $n$ distinct types of coupons, when $m$ increases with $n$. For fixed $m$, Erdős and Rényi proved that $\mathbb P(T_{n,m}\leq n\log n+(m-1)n\log\log n-n\log (m-1)!+θn)$ converges to $\mathcal G(θ)$, for every $θ\in \mathbb R$, as $n \to \infty$, where $\mathcal G$ is the standard Gumbel distribution function, and they asked what happens when $m=m(n)$ increases with $n$. We give a complete answer to this question. More precisely, for every increasing sequence $m=m(n)$, we determine explicit sequences $t_{n,m}$ and $w_{n,m}$ satisfying $w_{n,m}/t_{n,m}\to0$ such that $\mathbb P(T_{n,m}\leq t_{n,m}+θw_{n,m})\to\mathcal G(θ)$ for every $θ\in\mathbb R$. We also determine the corresponding asymptotic behavior of $\mathbb E[T_{n,m}]$. To prove these results, we present a methodology, inspired by Poissonization, that can be applied to determine the asymptotic behaviors of standardized hitting times of discrete-time stochastic processes.