Depth properties of scaled attachment random recursive trees

DOI10.1002/RSA.20391MaRDI QIDQ2909243zbMATH OpenOpenAlexWikidataFDO

Authors Omar Fawzi, Nicolas Fraiman, Luc Devroye

Publication date 30 August 2012

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

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

zbMATH Keywords

renewal processheightrandom treessecond moment methodpower of choice

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(10)

• The height of scaled attachment random recursive trees
• Longest path distance in random circuits
• Limit distribution of the degrees in scaled attachment random recursive trees
• It's a small world for random surfers
• Community modulated recursive trees and population dependent branching processes
• Depths in random recursive metric spaces
• 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
• The height of depth-weighted random recursive trees

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)