![]() |
Discrete Mathematics & Theoretical Computer Science |
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.
Source : ScholeXplorer
IsRelatedTo DOI 10.1002/0471667196.ess2066 Source : ScholeXplorer IsRelatedTo DOI 10.1002/0471667196.ess2066.pub2 Source : ScholeXplorer IsRelatedTo DOI 10.1002/9781118445112.stat02980 Source : ScholeXplorer IsRelatedTo DOI 10.1007/978-1-4612-0865-5_26 Source : ScholeXplorer IsRelatedTo DOI 10.1080/01621459.1963.10500830
|