The Library
Speed and concentration of the covering time for structured coupon collectors
Tools
Falgas-Ravry, Victor, Larsson, Joel and Markström, Klas (2020) Speed and concentration of the covering time for structured coupon collectors. Advances in Applied Probability, 52 (2). pp. 433-462. doi:10.1017/apr.2020.5 ISSN 0001-8678.
|
PDF
WRAP-speed-concentration-covering-coupon-collectors-Larsson-2019.pdf - Accepted Version - Requires a PDF viewer. Download (1165Kb) | Preview |
Official URL: http://dx.doi.org/10.1017/apr.2020.5
Abstract
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 Xi are 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.
Item Type: | Journal Article | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||||||
Library of Congress Subject Headings (LCSH): | Combinatorial probabilities , Concentration functions, Computer algorithms. | ||||||||||||
Journal or Publication Title: | Advances in Applied Probability | ||||||||||||
Publisher: | Applied Probability Trust | ||||||||||||
ISSN: | 0001-8678 | ||||||||||||
Official Date: | June 2020 | ||||||||||||
Dates: |
|
||||||||||||
Volume: | 52 | ||||||||||||
Number: | 2 | ||||||||||||
Page Range: | pp. 433-462 | ||||||||||||
DOI: | 10.1017/apr.2020.5 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Reuse Statement (publisher, data, author rights): | This article has been published in a revised form in Advances in Applied Probability http://doi.org/10.1017/apr.2020.5. This version is free to view and download for private research and study only. Not for re-distribution, re-sale or use in derivative works. © Applied Probability Trust 2020 | ||||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||||
Date of first compliant deposit: | 12 December 2019 | ||||||||||||
Date of first compliant Open Access: | 11 February 2021 | ||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||
Related URLs: | |||||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year