Rayleigh processes, real trees, and root growth with re-grafting

DOI10.1007/S00440-004-0411-6zbMATH Open1086.60050arXivmath/0402293OpenAlexW2129073925MaRDI QIDQ816985FDOQ816985

Steven Neil Evans, Anita Winter, Jim Pitman

Publication date: 2 March 2006

Published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Abstract: The real trees form a class of metric spaces that extends the class of trees with edge lengths by allowing behavior such as infinite total edge length and vertices with infinite branching degree. Aldous's Brownian continuum random tree, the random tree-like object naturally associated with a standard Brownian excursion, may be thought of as a random compact real tree. The continuum random tree is a scaling limit as N tends to infinity of both a critical Galton-Watson tree conditioned to have total population size N as well as a uniform random rooted combinatorial tree with N vertices. The Aldous--Broder algorithm is a Markov chain on the space of rooted combinatorial trees with N vertices that has the uniform tree as its stationary distribution. We construct and study a Markov process on the space of all rooted compact real trees that has the continuum random tree as its stationary distribution and arises as the scaling limit as N tends to infinity of the Aldous--Broder chain. A key technical ingredient in this work is the use of a pointed Gromov--Hausdorff distance to metrize the space of rooted compact real trees.

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

Recommendations

• The continuum random tree. I
• The continuum random tree. III
• scientific article; zbMATH DE number 19286
• Random trees and applications
• Random real trees

zbMATH Keywords

Hausdorff metricBrownian excursionpiecewise-deterministic Markov processGromov-Hausdorff metricAldous-Broder algorithmContinuum random tree

Mathematics Subject Classification ID

Probability measures on topological spaces (60B05) Probability theory on algebraic and topological structures (60B99) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Continuous-time Markov processes on discrete state spaces (60J27)

Cites Work

• Title not available (Why is that?)
• Geometry of the space of phylogenetic trees
• Title not available (Why is that?)
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• A course in metric geometry
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Probabilistic and fractal aspects of Lévy trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• Metric structures for Riemannian and non-Riemannian spaces. Transl. from the French by Sean Michael Bates. With appendices by M. Katz, P. Pansu, and S. Semmes. Edited by J. LaFontaine and P. Pansu
• \(\mathbb{R}\)-trees in topology, geometry, and group theory
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
• Title not available (Why is that?)
• The continuum random tree. III
• A Markovian analysis of additive-increase multiplicative-decrease algorithms
• The continuum random tree. I
• \(T\)-theory: An overview
• Title not available (Why is that?)
• Recursive self-similarity for random trees, random triangulations and Brownian excursion
• Triangulating the Circle, at Random
• Stationary distributions for piecewise-deterministic Markov processes
• The real tree
• The Gromov topology on \({\mathbb{R}}\)-trees
• Stability of Piecewise-Deterministic Markov Processes
• A proof of the Markov chain tree theorem
• Title not available (Why is that?)
• Λ-trees and their applications
• Jumping Markov processes
• \(\mathbb{R}\)-trees and symmetric differences of sets
• Snakes and spiders: Brownian motion on \(\mathbb{R}\)-trees
• Stationary Markov processes related to stable Ornstein-Uhlenbeck processes and the additive coalescent
• A class of piecewise deterministic Markov processes
• Title not available (Why is that?)
• Mixing Time for a Markov Chain on Cladograms
• Title not available (Why is that?)
• ON THE DERIVATIVE AND THE UPCROSSINGS OF THE RAYLEIGH PROCESS1

Cited In (68)

• Exact simulation of the genealogical tree for a stationary branching population and application to the asymptotics of its total length
• Regenerative real trees
• Scaling limits of slim and fat trees
• Continuum random trees and branching processes with immigration
• The Brownian map is the scaling limit of uniform random plane quadrangulations
• The exact packing measure of Lévy trees
• Coloured Loop-Erased Random Walk on the Complete Graph
• Scaling limit of the subdiffusive random walk on a Galton-Watson tree in random environment
• A tree approach to \(p\)-variation and to integration
• Inverting the cut-tree transform
• Scaling Limits of Markov-Branching Trees and Applications
• Critical random graphs and the differential equations technique
• Totally ordered measured trees and splitting trees with infinite variation
• Recursive construction of continuum random trees
• Tree-valued Fleming-Viot dynamics with mutation and selection
• The CRT is the scaling limit of unordered binary trees
• Dynamical pruning of rooted trees with applications to 1-D ballistic annihilation
• Wasserstein distance and metric trees
• Scaling limit of the recurrent biased random walk on a Galton-Watson tree
• Genealogy of catalytic branching models
• Convergence of simple random walks on random discrete trees to Brownian motion on the continuum random tree
• Random real trees
• Probabilistic and fractal aspects of Lévy trees
• Growth of Lévy trees
• Hereditary tree growth and Lévy forests
• Packing and Hausdorff Measures of Stable Trees
• Tree-valued resampling dynamics martingale problems and applications
• Limit of normalized quadrangulations: the Brownian map
• Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees
• Convergence of bi-measure \(\mathbb{R}\)-trees and the pruning process
• Random self-similar trees: a mathematical theory of Horton laws
• Scaling limit of dynamical percolation on critical Erdős-Rényi random graphs
• A binary embedding of the stable line-breaking construction
• Invariance and attraction properties of Galton-Watson trees
• Subtree prune and regraft: a reversible real tree-valued Markov process
• The Brownian Castle
• Exit times for an increasing Lévy tree-valued process
• Convergence in distribution of random metric measure spaces (\(\Lambda \)-coalescent measure trees)
• Dynamics of the time to the most recent common ancestor in a large branching population
• The Brownian cactus. I: Scaling limits of discrete cactuses
• Scaling limits of \(k\)-ary growing trees
• Hausdorff measure of arcs and Brownian motion on Brownian spatial trees
• The Brownian Web as a random \(\mathbb{R} \)-tree
• Exchangeable hierarchies and mass-structure of weighted real trees
• Loop-erased random walk on finite graphs and the Rayleigh process
• Metrics on sets of interval partitions with diversity
• Scaling limits of the three-dimensional uniform spanning tree and associated random walk
• On the exponential functional of Markov Additive Processes, and applications to multi-type self-similar fragmentation processes and trees
• On trees invariant under edge contraction
• The forest associated with the record process on a Lévy tree
• Metrization of the Gromov-Hausdorff (-Prokhorov) topology for boundedly-compact metric spaces
• Population Dynamics and Random Genealogies
• Branching Processes -- A General Concept
• Growing random graphs with a preferential attachment structure
• Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic mod\-els
• Gromov-Hausdorff-Prokhorov convergence of vertex cut-trees of \(n\)-leaf Galton-Watson trees
• Branching trees I: concatenation and infinite divisibility
• Spinal partitions and invariance under re-rooting of continuum random trees
• Exceptionally small balls in stable trees
• Brownian motion on \(\mathbb R\)-trees
• Regenerative tree growth: binary self-similar continuum random trees and Poisson-Dirichlet compositions
• Reversal property of the Brownian tree
• A unified framework for generalizing the Gromov-Hausdorff metric
• Invariant Galton–Watson trees: metric properties and attraction with respect to generalized dynamical pruning
• Spaces of algebraic measure trees and triangulations of the circle
• Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes
• Totally ordered measured trees and splitting trees with infinite variation. II: Prolific skeleton decomposition
• Scaling limit of linearly edge-reinforced random walks on critical Galton-Watson trees

This page was built for publication: Rayleigh processes, real trees, and root growth with re-grafting

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