Random Structures and Algorithms · 2011 · 16 citations · 25 references
EngineeringDecision SciencesProbability TheoryPruning SystemsStochastic ProcessesBranching ProcessesProbabilistic CombinatoricsRandom WalksTree Height EstimationBranching Random WalksDepth-dependent PropertiesDiscrete Random VariablesRandom Trees
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{document} \begin{align*}\left\lfloor iX_i\right\rfloor\end{align*} \end{document} and X 0 ,…, 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 ∼μ ‐1 log n , H n ∼ α max log n and M n ∼ α min log n where μ,α max and α 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 ∼ e log n that does not use branching random walks.© 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011
25
Emergence of Scaling in Random Networks
Albert-Ĺaszló Barabási, Réka Albert · Science · 1999 · 36.4K citations · Full text
On the Altitude of Nodes in Random Trees
A. Meir, J. W. Moon · Canadian Journal of Mathematics · 1978 · 367 citations · Full text