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 treesArticle

Authors: Luc Devroye ; Omar Fawzi ORCID1; Nicolas Fraiman 1

  • 1 Department of Mathematics and Statistics [Montréal]

We study depth properties of a general class of random recursive trees where each node $n$ attaches to the random node $\lfloor nX_n \rfloor$ and $X_0, \ldots , X_n$ 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 $H_n$ of a SARRT is asymptotically given by $H_n \sim \alpha_{\max} \log n$ where $\alpha_{\max}$ is a constant depending only on the distribution of $X_0$ whenever $X_0$ has a bounded density. This gives a new elementary proof for the height of uniform random recursive trees $H_n \sim e \log n$ 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

1 Document citing this article

Consultation statistics

This page has been seen 223 times.
This article's PDF has been downloaded 179 times.