Name
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, ..., where the X-i are independent random variables with distribution given by X. The covering time T is the smallest integer t >= 0 such that boolean OR(t)(i=1) 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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1017/apr.2020.5 | ADVANCES IN APPLIED PROBABILITY |
Keywords | Field | DocType |
Coupon collector,concentration inequalities,combinatorial probability | Coupon,Discrete mathematics,Combinatorics,Random variable,Mathematics | Journal |
Volume | Issue | ISSN |
52.0 | 2 | 0001-8678 |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Victor Falgas-Ravry | 1 | 28 | 7.46 |
| Joel Larsson | 2 | 0 | 0.34 |
| Klas Markström | 3 | 162 | 25.84 |