DMTCS Proceedings, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)

Font Size:  Small  Medium  Large

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

Valid XHTML 1.0 Transitional