| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
The height of scaled attachment random recursive trees
Abstract : 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.
Cited literature [26 references]
https://hal.inria.fr/hal-01185586
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 4:33:17 PM
Last modification on : Thursday, June 18, 2020 - 12:32:05 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:46:32 AM
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 4:33:17 PM
Last modification on : Thursday, June 18, 2020 - 12:32:05 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:46:32 AM
File
dmAM0110.pdf
Publisher files allowed on an open archive