Depth properties of scaled attachment random recursive trees

DOI10.1002/RSA.20391zbMATH Open1247.05217arXiv1210.7168OpenAlexW3083134037WikidataQ62556722 ScholiaQ62556722MaRDI QIDQ2909243FDOQ2909243

Luc Devroye, Omar Fawzi, Nicolas Fraiman

Publication date: 30 August 2012

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: We study depth properties of a general class of random recursive trees where each node i attaches to the random node iX_i 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 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.

Full work available at URL: https://arxiv.org/abs/1210.7168

Recommendations

• The height of scaled attachment random recursive trees
• Limit distribution of the degrees in scaled attachment random recursive trees
• scientific article; zbMATH DE number 17686
• Note on the heights of random recursive trees and random m‐ary search trees
• High degrees in random recursive trees

zbMATH Keywords

renewal processheightrandom treessecond moment methodpower of choice

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80)

Cites Work

• Emergence of Scaling in Random Networks
• Probability Inequalities for Sums of Bounded Random Variables
• On the fluctuations of sums of random variables
• Random Trees
• A note on the height of binary search trees
• On the Application of the Borel-Cantelli Lemma
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Uniform recursive trees: branching structure and simple random downward walk
• Branching processes in the analysis of the heights of trees
• Distribution of nodes of a tree by degree
• Title not available (Why is that?)
• Note on the heights of random recursive trees and random m‐ary search trees
• The strong convergence of maximal degrees in uniform random recursive trees and dags
• On the Altitude of Nodes in Random Trees
• The total progeny in a branching process and a related random walk
• Title not available (Why is that?)
• Long and short paths in uniform random recursive dags
• On the Expected Depth of Random Circuits
• The power of choice in the construction of recursive trees
• The power of choice in growing trees
• Total Path Length for Random Recursive Trees
• On the depth of randomly generated circuits
• On the Variance of the Height of Random Binary Search Trees
• Distances in random plane-oriented recursive trees
• Title not available (Why is that?)
• A Probability Model of a Pyramid Scheme
• On the distribution of distances in recursive trees

Cited In (6)

• It's a small world for random surfers
• Community modulated recursive trees and population dependent branching processes
• Longest Path Distance in Random Circuits
• Asymptotic results on Hoppe trees and their variations
• A new approach to Pólya urn schemes and its infinite color generalization
• Nonuniform recursive trees with vertex attraction depending on their labels

This page was built for publication: Depth properties of scaled attachment random recursive trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2909243)