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

DOI10.1007/S00440-004-0411-6MaRDI QIDQ816985zbMATH OpenOpenAlexFDO

Authors 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)

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

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)

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.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3951715 (Why is no real title available?)
• scientific article; zbMATH DE number 4059693 (Why is no real title available?)
• scientific article; zbMATH DE number 19286 (Why is no real title available?)
• scientific article; zbMATH DE number 1256746 (Why is no real title available?)
• scientific article; zbMATH DE number 1344715 (Why is no real title available?)
• scientific article; zbMATH DE number 1984558 (Why is no real title available?)
• scientific article; zbMATH DE number 1535858 (Why is no real title available?)
• scientific article; zbMATH DE number 942202 (Why is no real title available?)
• scientific article; zbMATH DE number 1385418 (Why is no real title available?)
• scientific article; zbMATH DE number 1859371 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• scientific article; zbMATH DE number 871943 (Why is no real title available?)
• A Markovian analysis of additive-increase multiplicative-decrease algorithms
• A class of piecewise deterministic Markov processes
• A course in metric geometry
• A proof of the Markov chain tree theorem
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• Geometry of the space of phylogenetic trees
• Jumping Markov processes
• 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
• Mixing Time for a Markov Chain on Cladograms
• ON THE DERIVATIVE AND THE UPCROSSINGS OF THE RAYLEIGH PROCESS1
• Probabilistic and fractal aspects of Lévy trees
• Recursive self-similarity for random trees, random triangulations and Brownian excursion
• Snakes and spiders: Brownian motion on \(\mathbb{R}\)-trees
• Stability of Piecewise-Deterministic Markov Processes
• Stationary Markov processes related to stable Ornstein-Uhlenbeck processes and the additive coalescent
• Stationary distributions for piecewise-deterministic Markov processes
• The Gromov topology on \({\mathbb{R}}\)-trees
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
• The continuum random tree. I
• The continuum random tree. III
• The real tree
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
• Triangulating the Circle, at Random
• \(T\)-theory: An overview
• \(\mathbb{R}\)-trees and symmetric differences of sets
• \(\mathbb{R}\)-trees in topology, geometry, and group theory
• Λ-trees and their applications

Cited in

(71)

• Continuum random trees and branching processes with immigration
• Regenerative real trees
• Exact simulation of the genealogical tree for a stationary branching population and application to the asymptotics of its total length
• The Brownian map is the scaling limit of uniform random plane quadrangulations
• Scaling limits of slim and fat trees
• The exact packing measure of Lévy trees
• Reversal property of the Brownian tree
• A unified framework for generalizing the Gromov-Hausdorff metric
• Doob-Martin boundary of Rémy's tree growth chain
• Packing and Hausdorff measures of stable 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
• Invariant Galton–Watson trees: metric properties and attraction with respect to generalized dynamical pruning
• Branching processes -- a general concept
• Recursive construction of continuum random trees
• Tree-valued Fleming-Viot dynamics with mutation and selection
• Dynamical pruning of rooted trees with applications to 1-D ballistic annihilation
• The CRT is the scaling limit of unordered binary trees
• Scaling limit of the recurrent biased random walk on a Galton-Watson tree
• Genealogy of catalytic branching models
• Wasserstein distance and metric trees
• 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
• Hereditary tree growth and Lévy forests
• Spaces of algebraic measure trees and triangulations of the circle
• Growth of Lévy trees
• Tree-valued resampling dynamics martingale problems and applications
• Limit of normalized quadrangulations: the Brownian map
• Projections of the Aldous chain on binary trees: intertwining and consistency
• 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
• Invariance and attraction properties of Galton-Watson trees
• A binary embedding of the stable line-breaking construction
• Subtree prune and regraft: a reversible real tree-valued Markov process
• Exit times for an increasing Lévy tree-valued process
• The Brownian Castle
• 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
• 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
• Scaling limits of k-ary growing trees
• The Brownian cactus. I: Scaling limits of discrete cactuses
• Hausdorff measure of arcs and Brownian motion on Brownian spatial trees
• 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
• The Brownian Web as a random \(\mathbb{R} \)-tree
• Scaling limit of linearly edge-reinforced random walks on critical Galton-Watson trees
• On trees invariant under edge contraction
• Scaling limits of the three-dimensional uniform spanning tree and associated random walk
• The forest associated with the record process on a Lévy tree
• Metrization of the Gromov-Hausdorff (-Prokhorov) topology for boundedly-compact metric spaces
• On the exponential functional of Markov Additive Processes, and applications to multi-type self-similar fragmentation processes and trees
• Population Dynamics and Random Genealogies
• Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic mod\-els
• Growing random graphs with a preferential attachment structure
• Gromov-Hausdorff-Prokhorov convergence of vertex cut-trees of \(n\)-leaf Galton-Watson trees
• Spinal partitions and invariance under re-rooting of continuum random trees
• Branching trees I: concatenation and infinite divisibility
• Exceptionally small balls in stable trees
• Brownian motion on \(\mathbb R\)-trees
• Probability and real trees. Ecole d'Eté de Probabilités de Saint-Flour XXXV -- 2005. Lecture given at the Saint-Flour probability summer school, July 6--23, 2005.
• Regenerative tree growth: binary self-similar continuum random trees and Poisson-Dirichlet compositions

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)