Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Speed and concentration of the covering time for structured coupon collectors

Falgas-Ravry, Victor ; Larsson, Joel LU orcid and Markström, Klas (2020) In Advances in Applied Probability 52(2). p.433-462
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 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 the union of the first t Xi's equal 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,... (More)
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 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 the union of the first t Xi's equal 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.
(Less)
Please use this url to cite or link to this publication:
author
; and
publishing date
type
Contribution to journal
publication status
published
subject
keywords
concentration inequalities, combinatorial mathematics, Probability theory, Coupon collector, combinatorial probability
in
Advances in Applied Probability
volume
52
issue
2
pages
30 pages
publisher
Applied Probability Trust
external identifiers
  • scopus:85089483359
ISSN
0001-8678
DOI
10.1017/apr.2020.5
language
English
LU publication?
no
id
bf00ffb6-10b9-48f5-8883-b20bf1665b65
date added to LUP
2020-09-18 15:34:49
date last changed
2022-04-19 00:49:52
@article{bf00ffb6-10b9-48f5-8883-b20bf1665b65,
  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 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 the union of the first t Xi's equal 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.<br/><br/>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.<br/>}},
  author       = {{Falgas-Ravry, Victor and Larsson, Joel and Markström, Klas}},
  issn         = {{0001-8678}},
  keywords     = {{concentration inequalities; combinatorial mathematics; Probability theory; Coupon collector; combinatorial probability}},
  language     = {{eng}},
  month        = {{07}},
  number       = {{2}},
  pages        = {{433--462}},
  publisher    = {{Applied Probability Trust}},
  series       = {{Advances in Applied Probability}},
  title        = {{Speed and concentration of the covering time for structured coupon collectors}},
  url          = {{http://dx.doi.org/10.1017/apr.2020.5}},
  doi          = {{10.1017/apr.2020.5}},
  volume       = {{52}},
  year         = {{2020}},
}