The impatient collector

06/26/2019

∙

by   Anis Amri, et al.

∙

0

∙

share

In the coupon collector problem with n items, the collector needs a random number of tries T_n≃ n n to complete the collection. Also, after nt tries, the collector has secured approximately a fraction ζ_∞(t)=1-e^-t of the complete collection, so we call ζ_∞ the (asymptotic) completion curve. In this paper, for ν>0, we address the asymptotic shape ζ (ν,.) of the completion curve under the condition T_n≤( 1+ν) n, i.e. assuming that the collection is 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.