Article contents
Tight bound of random interval packing
Published online by Cambridge University Press: 14 July 2016
Abstract
Consider n random intervals I1, …, IN chosen by selecting endpoints independently from the uniform distribution. A packing of I1, …, IN is a disjoint sub-collection of these intervals: its wasted space is the measure of the set of points not covered by the packing. We investigate the random variable WN equal to the smallest wasted space among all packings. Coffman, Poonen and Winkler proved that EWN is of order (log N)2/N. We provide a sharp estimate of log P(WN ≥ t (log N)2 / N) and log P(WN ≤ t (log N)2 / N) for all values of t.
MSC classification
- Type
- Research Papers
- Information
- Copyright
- Copyright © Applied Probability Trust 1998
Footnotes
Research supported in part by NSF contract DMS-9303188.
References
- 2
- Cited by