Correction terms for the height of weighted recursive trees

DOI10.1214/21-AAP1756zbMATH Open1498.05059arXiv2101.01156OpenAlexW3118453904MaRDI QIDQ2083274FDOQ2083274

Authors: Michel Pain, Delphin Sénizergues 

Publication date: 10 October 2022

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Abstract: Weighted recursive trees are built by adding successively vertices with predetermined weights to a tree: each new vertex is attached to a parent chosen randomly proportionally to its weight. Under some assumptions on the sequence of weights, the first order for the height of such trees has been recently established in [Electron. J. Probab. 26 (2021), Paper No. 80] by one of the authors. In this paper, we obtain the second and third orders in the asymptotic expansion of the height of weighted recursive trees, under similar assumptions. Our methods are inspired from those used to prove similar results for branching random walks. Our results also apply to a related model of growing trees, called the preferential attachment tree with additive fitnesses.

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

Recommendations

• Geometry of weighted recursive and affine preferential attachment trees
• On weighted heights of random trees
• Fine asymptotics for the maximum degree in weighted recursive trees with bounded random weights
• Large deviations for the weighted height of an extended class of trees
• Weighted height of random trees

zbMATH Keywords

random treesweighted recursive treesasymptotic height

Mathematics Subject Classification ID

Extreme value theory; extremal stochastic processes (60G70) Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Signed and weighted graphs (05C22)

Cites Work

• Title not available (Why is that?)
• An approximation theorem for the Poisson binomial distribution
• Random Trees
• Minimal position and critical martingale convergence in branching random walks, and directed polymers on disordered trees
• A conditional limit theorem for the frontier of a branching Brownian motion
• Convergence of solutions of the Kolmogorov equation to travelling waves
• On growing random binary trees
• Minima in branching random walks
• Convergence in law of the minimum of a branching random walk
• A note on the height of binary search trees
• Two Probability Models of Pyramid or Chain Letter Schemes Demonstrating that Their Promotional Claims are Unreliable
• Maximal displacement of branching brownian motion
• Branching processes in the analysis of the heights of trees
• Distribution of nodes of a tree by degree
• Note on the heights of random recursive trees and random m‐ary search trees
• Growing random networks with fitness
• The Seneta-Heyde scaling for the branching random walk
• A phase transition for preferential attachment models with additive fitness
• An analytic approach to the height of binary search trees. II
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Poisson-Dirichlet branching random walks
• The height of a random binary search tree
• Asymptotic analysis of Hoppe trees
• Title not available (Why is that?)
• Exact Kolmogorov and total variation distances between some familiar discrete distributions
• The near-critical Gibbs measure of the branching random walk
• Asymptotic results on Hoppe trees and their variations
• Geometry of weighted recursive and affine preferential attachment trees
• On the asymptotic behaviour of random recursive trees in random environments
• Random walks with preferential relocations and fading memory: a study through random recursive trees
• Cyclic behavior of maxima in a hierarchical summation scheme
• Oscillations in the height of the Yule tree and application to the binary search tree

Cited In (9)

• Geometry of weighted recursive and affine preferential attachment trees
• Large deviation principle for a stochastic process with random reinforced relocations
• Fine asymptotics for the maximum degree in weighted recursive trees with bounded random weights
• Trees with product-form random weights
• The maximal degree in random recursive graphs with random weights
• Height of weighted recursive trees with sub-polynomially growing total weight
• Trees with exponential height dependent weight
• On the asymptotic behaviour of random recursive trees in random environments
• The height of depth-weighted random recursive trees

This page was built for publication: Correction terms for the height of weighted recursive trees

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