Luc Devroye ; Omar Fawzi ; Nicolas Fraiman
-
The height of scaled attachment random recursive trees
dmtcs:2788 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2010,
DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
-
https://doi.org/10.46298/dmtcs.2788
The height of scaled attachment random recursive treesConference paper
Authors: Luc Devroye ; Omar Fawzi 1,2; Nicolas Fraiman 1,2
NULL##0000-0001-8491-0359##NULL
Luc Devroye;Omar Fawzi;Nicolas Fraiman
1 Department of Mathematics and Statistics [Montréal]
2 Departement of Mathematics and Statistics [Montréal, McGill University]
We study depth properties of a general class of random recursive trees where each node n attaches to the random node ⌊nXn⌋ and X0,…,Xn is a sequence of i.i.d. random variables taking values in [0,1). We call such trees scaled attachment random recursive trees (SARRT). We prove that the height Hn of a SARRT is asymptotically given by Hn∼αmaxlogn where αmax is a constant depending only on the distribution of X0 whenever X0 has a bounded density. This gives a new elementary proof for the height of uniform random recursive trees Hn∼elogn that does not use branching random walks.
Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: Random recursive tree,Random web model,Power of choice,Renewal process,Second moment method,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
Funding:
Source : OpenAIRE Graph
Funder: Natural Sciences and Engineering Research Council of Canada
Bibliographic References
1 Document citing this article
Mark Korenblit;Vadim Talis;Ilya Levin, Studies in computational intelligence, One-Max Constant-Probability Models for Complex Networks, pp. 181-188, 2014, 10.1007/978-3-319-05401-8_17.