Cutoff profile for the coupon collector with many collections
Abstract
We solve the problem posed by Erdős and Rényi in $1961$ about the limiting distribution of the number of draws Tn,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 ℙ(Tn,m≤ nlog n+(m−1)nloglog n−nlog (m−1)!+θn) converges to $ \mathcal G(θ)$, for every θ∈ ℝ, as n → ∞, where 𝒢 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 tn,m and wn,m satisfying wn,m/tn,m→0 such that ℙ(Tn,m≤ tn,m+θwn,m)→𝒢(θ) for every θ∈ℝ. We also determine the corresponding asymptotic behavior of 𝔼[Tn,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.
Related
- The Fragile Coupon Collector: Random Deadlines, Critical Fragility, and Optimal Sampling
- Cutoff profile for the balanced generalized Bernoulli--Laplace model
- Cutoff and a Gaussian-shift profile for the Rudvalis shuffle
- Multi-Objective Fractional-Order Control Design for Solar Collector Systems Under Parameter Perturbations and Stability Constraints
- Edge and spectral conditions for rainbow pancyclicity in graph collections
BibTeX
@misc{castro2026cutoff,
title = {{Cutoff profile for the coupon collector with many collections}},
author = {Maria Eliza Castro and Rodrigo Marinho},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33199},
eprint = {2610.33199},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33199},
}
RIS
TY - UNPB
TI - Cutoff profile for the coupon collector with many collections
AU - Maria Eliza Castro
AU - Rodrigo Marinho
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.33199
UR - https://arxiv.org/abs/2610.33199
AB - 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 ℙ(T_n,m≤ nlog n+(m−1)nloglog n−nlog (m−1)!+θn) converges to $ \mathcal G(θ)$, for every θ∈ ℝ, as n → ∞, where 𝒢 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→0 such that ℙ(T_n,m≤ t_n,m+θw_n,m)→𝒢(θ) for every θ∈ℝ. We also determine the corresponding asymptotic behavior of 𝔼[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.
ER -