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

Asymptotic Analysis of Hoppe Trees

Part of: Limit theorems Discrete mathematics in relation to computer science Stochastic processes Combinatorial probability

Published online by Cambridge University Press:  30 January 2018

Kevin Leckey  and
Ralph Neininger
Kevin Leckey*
Affiliation:
Goethe University Frankfurt
Ralph Neininger*
Affiliation:
Goethe University Frankfurt
*
∗ Postal address: Institute for Mathematics, Goethe University, 60054 Frankfurt am Main, Germany.
∗ Postal address: Institute for Mathematics, Goethe University, 60054 Frankfurt am Main, Germany.
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.

We introduce and analyze a random tree model associated to Hoppe's urn. The tree is built successively by adding nodes to the existing tree when starting with the single root node. In each step a node is added to the tree as a child of an existing node, where these parent nodes are chosen randomly with probabilities proportional to their weights. The root node has weight ϑ>0, a given fixed parameter, all other nodes have weight 1. This resembles the stochastic dynamic of Hoppe's urn. For ϑ=1, the resulting tree is the well-studied random recursive tree. We analyze the height, internal path length, and number of leaves of the Hoppe tree with n nodes as well as the depth of the last inserted node asymptotically as n→∞. Mainly expectations, variances, and asymptotic distributions of these parameters are derived.

Keywords

Hoppe urnrandom treeweak convergencemartingalecombinatorial probability

MSC classification

Primary: 60F05: Central limit and other weak theorems 60C05: Combinatorial probability
Secondary: 60G42: Martingales with discrete parameter 68R05: Combinatorics
Type
Research Article
Information
Journal of Applied Probability , Volume 50 , Issue 1 , March 2013 , pp. 228 - 238
Copyright
Copyright © Applied Probability Trust 2013 

References

Abramowitz, M. and Stegun, I. A. (1964). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (Natl. Bureau Standards Appl. Math. Ser. 55). Government Printing Office, Washington, DC.Google Scholar
Addario-Berry, L. and Ford, K. (2013). Poisson–Dirichlet branching random walks. Ann. Appl. Prob. 23, 283–307.CrossRefGoogle Scholar
Barbour, A. D., Holst, L. and Janson, S. (1992). Poisson Approximation (Oxford Stud. Prob. 2). The Clarendon Press, Oxford University Press, New York.CrossRefGoogle Scholar
Dobrow, R. P. and Fill, J. A. (1999). Total path length for random recursive trees. Combin. Prob. Comput. 8, 317–333.CrossRefGoogle Scholar
Dobrow, R. P. and Smythe, R. T. (1996). Poisson approximations for functionals of random trees. Random Structures Algorithms 9, 79–92.3.0.CO;2-8>CrossRefGoogle Scholar
Donnelly, P. and Tavaré, S. (1986). The ages of alleles and a coalescent. Adv. Appl. Prob. 18, 1–19. (Correction: 18 (1986), 1023.)CrossRefGoogle Scholar
Fill, J. A. and Janson, S. (2000). Smoothness and decay properties of the limiting Quicksort density function. In Mathematics and Computer Science (Versailles, 2000), Birkhäuser, Basel, pp. 53–64.CrossRefGoogle Scholar
Hall, P. and Heyde, C. C. (1980). Martingale Limit Theory and Its Application. Academic Press, New York.Google Scholar
Hoppe, F. M. (1986). Size-biased filtering of Poisson–Dirichlet samples with an application to partition structures in genetics. J. Appl. Prob. 23, 1008–1012.CrossRefGoogle Scholar
Leckey, K. (2011). Asymptotische Eigenschaften von Hoppe–{B}äumen. Masters Thesis, Goethe Universität Frankfurt a.M. Available at http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/24214.Google Scholar
Mahmoud, H. M. (1991). Limiting distributions for path lengths in recursive trees. Prob. Eng. Inf. Sci. 5, 53–59.CrossRefGoogle Scholar
Neininger, R. and Rüschendorf, L. (2004). A general limit theorem for recursive algorithms and combinatorial structures. Ann. Appl. Prob. 14, 378–418.CrossRefGoogle Scholar
Pitman, J. (2006). Combinatorial Stochastic Processes (Lecture Notes Math. 1875). Springer, Berlin.Google Scholar
Rösler, U. (2001). On the analysis of stochastic divide and conquer algorithms. Algorithmica 29, 238–261.CrossRefGoogle Scholar
Smythe, R. T. and Mahmoud, H. M. (1994). A survey of recursive trees. Teor. Imovı¯r. Mat. Statist. 51, 1–29. English translation: Theory Prob. Math. Statist. 51 (1995), 1-27.Google Scholar