Speed and concentration of the covering time for structured coupon collectors. (June 2020)

• Record Type: Journal Article
• Authors: Falgas-Ravry, Victor; Larsson, Joel; Markström, Klas
• Is Part Of: Advances in applied probability. Volume 52:Number 2(2020)
• Page Start: 433
• Page End: 462
• Publication Date: 2020-06
• Subjects: Coupon collector, -- concentration inequalities, -- combinatorial probability; 60C05, -- 05B40, -- 05C80, -- 60G99; Probabilities -- Periodicals; Stochastic models -- Periodicals; Electronic journals; Periodicals; 519.2
• DOI: 10.1017/apr.2020.5
• Languages: English
• ISSNs: 0001-8678

Abstract

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, \ldots $, where the $X_i$ are independent random variables with distribution given by X . The covering time T is the smallest integer $t\geq 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.