Depth Properties of scaled attachment random recursive trees
- 23 December 2011
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 41 (1) , 66-98
Abstract
We study depth properties of a general class of random recursive trees where each node i attaches to the random node \documentclass{article} \usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty} \begin{align*}\left\lfloor iX_i\right\rfloor\end{align*} and X0,…,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 typical depth Dn, the maximum depth (or height) Hn and the minimum depth Mn of a sarrt are asymptotically given by Dn ∼μ‐1 log n, Hn ∼ αmax log n and Mn ∼ αmin log n where μ,αmax and αmin are constants depending only on the distribution of X0 whenever X0 has a density. In particular, this gives a new elementary proof for the height of uniform random recursive trees Hn ∼ elog n that does not use branching random walks.© 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011
Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- The power of choice in growing treesThe European Physical Journal B, 2007
- On the distribution of distances in recursive treesJournal of Applied Probability, 1996
- The strong convergence of maximal degrees in uniform random recursive trees and dagsRandom Structures & Algorithms, 1995
- Note on the heights of random recursive trees and random m‐ary search treesRandom Structures & Algorithms, 1994
- A note on the height of binary search treesJournal of the ACM, 1986
- On the Altitude of Nodes in Random TreesCanadian Journal of Mathematics, 1978
- A Probability Model of a Pyramid SchemeThe American Statistician, 1977
- The total progeny in a branching process and a related random walkJournal of Applied Probability, 1969
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963
- On the application of the Borel-Cantelli lemmaTransactions of the American Mathematical Society, 1952