The height of scaled attachment random recursive trees
Luc Devroye, Omar Fawzi, Nicolas Fraiman
Abstract
We study depth properties of a general class of random recursive trees where each node n attaches to the random node ⌊nXn ⌋ and X0, &dots;, 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 ∼αmax logn 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 ∼e logn that does not use branching random walks.
Full Text: PostScript PDF