umu.sePublications
Change search
ReferencesLink to record
Permanent link

Direct link
Speed and concentration of the covering time for structured coupon collectors
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
(English)Manuscript (preprint) (Other academic)
Abstract [en]

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.

National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-121416OAI: oai:DiVA.org:umu-121416DiVA: diva2:932749
Available from: 2016-06-02 Created: 2016-06-02 Last updated: 2016-06-02

Open Access in DiVA

No full text

Other links

http://arxiv.org/abs/1601.04455

Search in DiVA

By author/editor
Larsson, Joel
By organisation
Department of Mathematics and Mathematical Statistics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 8 hits
ReferencesLink to record
Permanent link

Direct link