arXiv:2610.33199v1 Announce Type: new Abstract: We solve the problem posed by Erd\H{o}s and R\'enyi 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\H{o}s and R\'enyi proved that $\mathbb P(T_{n,m}\leq n\log n+(m-1)n\log\log n-n\log (m-1)!+\theta n)$ converges to $ \mathcal G(\theta)$, for every $\theta \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}+\theta w_{n,m})\to\mathcal G(\theta)$ for every $\theta\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.
Continue to arXiv Mathematics →You are being forwarded in 6s — stay on this page