Speed and concentration of the covering time for structured coupon collectors
(English)Manuscript (preprint) (Other academic)
Let V be an n-set, and let X be a random variable taking values in the powerset of V. Suppose we are given a sequence of random coupons X1,X2,…, where the Xiare independent random variables with distribution given by X. The covering time T is the smallest integer t≥0 such that ⋃ti=1Xi=V. The distribution of T is important in many applications in combinatorial probability, and has been extensively studied. However the literature has focussed 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.
Research subject Mathematics
IdentifiersURN: urn:nbn:se:umu:diva-121416OAI: oai:DiVA.org:umu-121416DiVA: diva2:932749