Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-22T21:58:20.774Z Has data issue: false hasContentIssue false
  • English
  • Français

Gaps in Discrete Random Samples

Part of: Limit theorems Combinatorial probability

Published online by Cambridge University Press:  14 July 2016

Rudolf Grübel  and
Paweł Hitczenko
Rudolf Grübel*
Affiliation:
Leibniz Universität Hannover
Paweł Hitczenko*
Affiliation:
Drexel University
*
∗Postal address: Institut für Mathematische Stochastik, Leibniz Universität Hannover, Postfach 6009, D-30060 Hannover, Germany. Email address: [email protected]
∗∗Postal address: Departments of Mathematics and Computer Science, Drexel University, 3141 Chestnut Str., Philadelphia, PA 19104, USA. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let (Xi)i∈ℕ be a sequence of independent and identically distributed random variables with values in the set ℕ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 {X1,…,Xn} of the first n values. We obtain necessary and sufficient conditions in terms of the tail sequence (qk)k∈ℕ0, qk=P(X1≥ k), for the gaps to vanish asymptotically as n→∞: these are ∑k=0∞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 distributionheavy taillight tailperiodicitiesSukhatme–Rényi representation

MSC classification

Secondary: 60C05: Combinatorial probability 60F99: None of the above, but in this section
Type
Research Article
Information
Journal of Applied Probability , Volume 46 , Issue 4 , December 2009 , pp. 1038 - 1051
Copyright
Copyright © Applied Probability Trust 2009 

Footnotes

Supported in part by the NSA grant #H98230-09-1-0062

References

[1] Bogachev, L. V., Gnedin, A. V. and Yakubovich, Y. V. (2008). On the variance of the number of occupied boxes. Adv. Appl. Math. 40, 401–432.CrossRefGoogle Scholar
[2] Bruss, F. T. and Grübel, R. (2003). On the multiplicity of the maximum in a discrete random sample. Ann. Appl. Prob. 13, 1252–1263.CrossRefGoogle Scholar
[3] Gnedin, A., Hansen, B. and Pitman, J. (2007). Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws. Prob. Surveys 4, 146–171.CrossRefGoogle Scholar
[4] Goh, W. M. Y. and Hitczenko, P. (2007). Gaps in samples of geometrically distributed random variables. Discrete Math. 307, 2871–2890.CrossRefGoogle Scholar
[5] Grübel, R. (2007). Distributional asymptotics in the analysis of algorithms: Periodicities and discretization. Discrete Math. Theoret. Comput. Sci. AH, 451–460.Google Scholar
[6] Hitczenko, P. and Knopfmacher, A. (2005). Gap-free compositions and gap-free samples of geometric random variables. Discrete Math. 294, 225–239.CrossRefGoogle Scholar
[7] Hwang, H.-K. and Janson, S. (2008). Local limit theorems for finite and infinite urn models. Ann. Prob. 36, 992–1022.CrossRefGoogle Scholar
[8] Karlin, S. (1967). Central limit theorems for certain infinite urn schemes. J. Math. Mech. 17, 373–401.Google Scholar
[9] Louchard, G. and Prodinger, H. (2008). On gaps and unoccupied urns in sequences of geometrically distributed random variables. Discrete Math. 308, 1538–1562.CrossRefGoogle Scholar
[10] Shorack, G. R. and Wellner, J. A. (1986). Empirical Processes with Applications to Statistics. John Wiley, New York.Google Scholar