\input zb-basic
\input zb-ioport
\iteman{io-port 06074028}
\itemau{Devroye, Luc; Fawzi, Omar; Fraiman, Nicolas}
\itemti{Depth properties of scaled attachment random recursive trees.}
\itemso{Random Struct. Algorithms 41, No. 1, 66-98 (2012).}
\itemab
Summary: We study depth properties of a general class of random recursive trees where each node $i$ attaches to the random node $\lfloor i X_{i}\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 typical depth $D_{n}$, the maximum depth (or height) $H_{n}$ and the minimum depth $M_{n}$ of a SARRT are asymptotically given by $D_{n} \sim \mu^{-1} \log n, H_{n} \sim \alpha _{max} \log n$ and $M_{n} \sim \alpha _{min} \log n$ where $\mu ,\alpha _{max}$ and $\alpha _{min}$ are constants depending only on the distribution of $X_{0}$ whenever $X_{0}$ has a density. In particular, 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.
\itemrv{~}
\itemcc{}
\itemut{random trees; height; power of choice; renewal process; second moment method}
\itemli{doi:10.1002/rsa.20391}
\end