The impatient collector

Abstract

In the coupon collector problem with $n$ items, the collector needs a random number of tries $T_n\simeq n\ln n$ to complete the collection. Also, after $nt$ tries, the collector has secured approximately a fraction ${\zeta }_{\infty }(t)=1-e^{-t}$ of the complete collection, so we call ${\zeta }_{\infty }$ the (asymptotic) \emph{completion curve}. In this paper, for $\nu >0$, we address the asymptotic shape $\zeta (\nu ,.)$ of the completion curve under the condition $T_n\le \left(1+\nu \right)n$, i.e. assuming that the collection is \emph{completed unlikely fast}. As an application to the asymptotic study of complete accessible automata, we provide a new derivation of a formula due to Koršunov.