Speed and concentration of the covering time for structured coupon collectors. (June 2020) - Falgas-Ravry, Victor; Larsson, Joel; Markström, Klas
Abstract: Let V be an n -set, and let X be a random variable taking values in the power-set of V . Suppose we are given a sequence of random coupons $X_1, X_2, … $, where the $X_i$ are independent random variables with distribution given by X . The covering time T is the smallest integer $t≥ 0$ such that $\bigcup_{i=1}^t X_i=V$ . The distribution of T is important in many applications in combinatorial probability, and has been extensively studied. However the literature has focused almost exclusively on the case where X is assumed to be symmetric and/or uniform in some way. In this paper we study the covering time for much more general random variables X ; we give general criteria for T being sharply concentrated around its mean, precise tools to estimate that mean, as well as examples where T fails to be concentrated and when structural properties in the distribution of X allow for a very different behaviour of T relative to the symmetric/uniform case.