Correction terms for the height of weighted recursive trees

DOI10.1214/21-AAP1756MaRDI QIDQ2083274zbMATH OpenOpenAlexFDO

Authors Michel Pain, Delphin Sénizergues

Publication date 10 October 2022

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

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

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)

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.

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

Cites work

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

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)