Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-23T05:48:31.133Z Has data issue: false hasContentIssue false
  • English
  • Français

Pruned Discrete Random Samples

Part of: Markov processes Limit theorems Combinatorial probability

Published online by Cambridge University Press:  30 January 2018

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 Street, 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 independent and identically distributed random variables with values in ℕ0. We transform (‘prune’) the sequence {X1,…,Xn},n∈ ℕ, of discrete random samples into a sequence {0,1,2,…,Yn}, n∈ ℕ, of contiguous random sets by replacing Xn+1 with Yn +1 if Xn+1 >Yn. We consider the asymptotic behaviour of Yn as n→∞. Applications include path growth in digital search trees and the number of tables in Pitman's Chinese restaurant process if the latter is conditioned on its limit value.

Keywords

Chinese restaurant processdigital search treesgeometric distributionmaximatail behaviour

MSC classification

Primary: 60C05: Combinatorial probability
Secondary: 60F99: None of the above, but in this section 60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
Type
Research Article
Information
Journal of Applied Probability , Volume 50 , Issue 2 , June 2013 , pp. 542 - 556
Copyright
© Applied Probability Trust 

Footnotes

Partially supported by a grant from Simons Foundation (grant no. 208766).

References

Bingham, N. H., Goldie, C. M. and Teugels, J. L. (1987). Regular Variation (Encyclopedia Math. Appl. 27). Cambridge University Press.Google Scholar
Brémaud, P. (1999). Markov Chains (Texts Appl. Math. 31). Springer, New York.Google Scholar
Dennert, F. and Grübel, R. (2007). Renewals for exponentially increasing lifetimes, with an application to digital search trees. Ann. Appl. Prob. 17, 676–687.Google Scholar
Drmota, M. (2009). Random Trees. SpringerWienNewYork, Vienna.Google Scholar
Evans, S. N., Grübel, R. and Wakolbinger, A. (2012). Trickle-down processes and their boundaries. Electron J. Prob. 17, 58pp.Google Scholar
Grübel, R. (2007). Distributional asymptotics in the analysis of algorithms: periodicities and discretization. In AofA '07 Conf. on Analysis of Algorithms (Discrete Math. Theoret. Comput. Sci. Proc. AH), pp. 451–462.Google Scholar
Grübel, R. and Hitczenko, P. (2009). Gaps in discrete random samples. J. Appl. Prob. 46, 1038–1051.Google Scholar
Kallenberg, O. (1997). Foundations of Modern Probability. Springer, New York.Google Scholar
Knuth, D. E. (1973). The Art of Computer Programming, Vol. 3. Addison-Wesley, Reading, MA.Google Scholar
Mahmoud, H. M. (1992). Evolution of Random Search Trees. John Wiley, New York.Google Scholar
Pitman, J. (2006). Combinatorial Stochastic Processes (Lecture Notes Math. 1875). Springer, Berlin.Google Scholar