Journal article
GAPS IN DISCRETE RANDOM SAMPLES
Journal of applied probability, v 46(4), pp 1038-1051
01 Dec 2009
Abstract
Let (X-i)(i is an element of N) be a sequence of independent and identically distributed random variables with values in the set N-0 of nonnegative integers. Motivated by applications in enumerative combinatorics and analysis of algorithms we investigate the number of gaps and the length of the longest gap in the set {X-1, ... , X-n} of the first n values. We obtain necessary and sufficient conditions in terms of the tail sequence q(q(k))(k is an element of N0), q(k) = P(X-1 >= k), for the gaps to vanish asymptotically as n -> infinity: these are Sigma(infinity)(k=0) q(k+1)/q(k) < infinity and lim(k ->infinity) q(k+1)/q(k) = 0 for convergence almost surely and convergence in probability, respectively. We further show that the length of the longest gap tends to infinity in probability if q(k+1)/q(k) -> 1. For the family of geometric distributions, which can be regarded as the borderline case between the light-tailed and the heavy-tailed situations and which is also of particular interest in applications, we study the distribution of the length of the longest gap, using a construction based on the Sukhatme-Renyi representation of exponential orderstatistics to resolve the asymptotic distributional periodicities.
Metrics
Details
- Title
- GAPS IN DISCRETE RANDOM SAMPLES
- Creators
- Rudolf Gruebel - Leibniz University HannoverPawei Hitczenko - Drexel Univ, Philadelphia, PA 19104 USA
- Publication Details
- Journal of applied probability, v 46(4), pp 1038-1051
- Publisher
- Cambridge Univ Press
- Number of pages
- 14
- Grant note
- H98230-09-1-0062 / NSA; National Security Agency
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Mathematics
- Web of Science ID
- WOS:000273995700008
- Scopus ID
- 2-s2.0-76449098663
- Other Identifier
- 991019319093204721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- International collaboration
- Web of Science research areas
- Statistics & Probability