Details
| Original language | English |
|---|---|
| Pages (from-to) | 1038-1051 |
| Number of pages | 14 |
| Journal | Journal of applied probability |
| Volume | 46 |
| Issue number | 4 |
| Publication status | Published - Dec 2009 |
Abstract
Let (Xi)i∈N be a sequence of independent and identically distributed random variables with values in the set N0 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 {X1 ,.,Xn} of the first n values. We obtain necessary and sufficient conditions in terms of the tail sequence (qk) k∈N0 ,qk = P(X1 ≥ k), for the gaps to vanish asymptotically as n →∞: these are Σk Sigma;qk+1/qk < Σ and limk →Σ; qk+1/qk = 0 for convergence almost surely and convergence in probability, respectively. We further show that the length of the longest gap tends to Σ in probability if qk+1 /qk → 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- Rényi representation of exponential order statistics to resolve the asymptotic distributional periodicities.
Keywords
- Geometric distribution, Heavy tail, Light tail, Periodicities, Sukhatme-Rényi representation
ASJC Scopus subject areas
- Mathematics(all)
- Statistics and Probability
- Mathematics(all)
- General Mathematics
- Decision Sciences(all)
- Statistics, Probability and Uncertainty
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Journal of applied probability, Vol. 46, No. 4, 12.2009, p. 1038-1051.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Gaps in Discrete Random Samples
AU - Grübel, Rudolf
AU - Hitczenko, Paweł
PY - 2009/12
Y1 - 2009/12
N2 - Let (Xi)i∈N be a sequence of independent and identically distributed random variables with values in the set N0 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 {X1 ,.,Xn} of the first n values. We obtain necessary and sufficient conditions in terms of the tail sequence (qk) k∈N0 ,qk = P(X1 ≥ k), for the gaps to vanish asymptotically as n →∞: these are Σk Sigma;qk+1/qk < Σ and limk →Σ; qk+1/qk = 0 for convergence almost surely and convergence in probability, respectively. We further show that the length of the longest gap tends to Σ in probability if qk+1 /qk → 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- Rényi representation of exponential order statistics to resolve the asymptotic distributional periodicities.
AB - Let (Xi)i∈N be a sequence of independent and identically distributed random variables with values in the set N0 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 {X1 ,.,Xn} of the first n values. We obtain necessary and sufficient conditions in terms of the tail sequence (qk) k∈N0 ,qk = P(X1 ≥ k), for the gaps to vanish asymptotically as n →∞: these are Σk Sigma;qk+1/qk < Σ and limk →Σ; qk+1/qk = 0 for convergence almost surely and convergence in probability, respectively. We further show that the length of the longest gap tends to Σ in probability if qk+1 /qk → 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- Rényi representation of exponential order statistics to resolve the asymptotic distributional periodicities.
KW - Geometric distribution
KW - Heavy tail
KW - Light tail
KW - Periodicities
KW - Sukhatme-Rényi representation
UR - http://www.scopus.com/inward/record.url?scp=76449098663&partnerID=8YFLogxK
U2 - 10.1239/jap/1261670687
DO - 10.1239/jap/1261670687
M3 - Article
AN - SCOPUS:76449098663
VL - 46
SP - 1038
EP - 1051
JO - Journal of applied probability
JF - Journal of applied probability
SN - 0021-9002
IS - 4
ER -