Markström, Klas , Falgas-Ravry, Victor & Larsson, Joel | 2020
Journal of Applied Probability
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 , where the are independent random variables with distribution given by X. The covering time T is the smallest integer such that . 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.
