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

By Steven N. Evans, Jim Pitman, A. Winter. 2004

158 citations recorded by the source corpus.

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→∞ 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→∞ 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.Berkeley Statistics Technical Report No. 654 (February 2004), revised October 2004. To appear in Probability Theory and Related Fields.

Subfields: Mathematical Physics, Statistics and Probability, Signal Processing

View Paper: https://www.semanticscholar.org/paper/002834293aabbc034c32d6406906638fe39bd431

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Mathematical Physics

In Statistics and Probability

In Signal Processing

Citations in the corpus

Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic models (2006, methodology): “It has been shown in [17] that Θ is a Polish space when endowed with the so-called pointed Gromov-Hausdorff distance dGH, where by definition the distance dGH((τ, ρ), (τ ′, ρ′))) is equal to the infimum of the quantities δ(r, r′) ∨ δH(T, T ′), where (T, r), (T ′, r′) are isometric embeddings of (τ, ”
Convergence in distribution of random metric measure spaces (Λ-coalescent measure trees) (2009, background): “On the other hand the space of all (isometry classes of compact) metric spaces, not carrying a measure, is complete and separable once equipped with the Gromov–Hausdorff metric (see, [ 11 ]).”
Spinal partitions and invariance under re-rooting of continuum random trees (2007, methodology): “An alternative formalism can be considered, via the set of equivalence classes of compact rooted R-trees endowed with the Gromov–Hausdorff distance, as developed in [16, 17].”
Limit of normalized quadrangulations: The Brownian map (2004, background): “Evans & al. [ 20 ], Le Gall [29], and Pitman [36].”
A note on the Gromov-Hausdorff-Prokhorov distance between (locally) compact metric measure spaces (2012, background): “Recently, the concept of Gromov-Hausdorff convergence has found striking applications in the field of probability theory, in the context of random graphs.”
The Brownian map is the scaling limit of uniform random plane quadrangulations (2011, background): “The space (M, dGH) is then a separable and complete metric space [11].”
Growth of Lévy trees (2005, methodology): “[16], we consider genealogical trees as tree-like metric spaces and more precisely as locally compact rooted real trees, whose precise definition is given in Sect.”
Probabilistic and fractal aspects of Lévy trees (2005, background): “It was noted in [13] that the set of equivalence classes of compact rooted R-trees, equipped with the Gromov-Hausdorff distance [15] is a Polish space.”
On the sphericity of scaling limits of random planar quadrangulations (2007, background): “nd subsets X,X′ ⊂ Z such that [X,δ] = X,[X′,δ] = X′, and such that the Hausdorﬀ distance between X and X′ in (Z,δ) is less than or equal to r. This turns M into a complete separable metric space, see [6] (this article focuses on compact R-trees, which form a closed subspace of M, but the proofs appl”
Conditioned Brownian trees (2005, unknown): “In this work it will be convenient to view marked trees as R-trees in the sense of [13] or [14] (see also Section 1 above).”
Invariance principle for variable speed random walks on trees (2014, background): “ all x,y∈ Twith x∈ [ρ,y]. To be in a position to capture that our variable speed motions are processes on “natural scale” we need the notion of a length measure. For R-trees it was ﬁrst introduced in [EPW06]. It turns out that this measure can be constructed on any separable 0-hyperbolic metric spac”
Scaling limits of Markov branching trees with applications to Galton–Watson and random unordered trees (2010, background): “It is well-known (this is an easy extension of the results of [20]) that M is a Polish space when endowed with the so-called pointed Gromov-Hausdorff distance dGH, where by definition the distance dGH((X, ρ), (X ′, ρ′)) is equal to the infimum of the quantities δ(φ(ρ), φ(ρ)) ∨ δH(φ(X), φ(X )) where ”
Random trees and applications (2005, methodology): “We briefly discuss some applications to various classes of “combinatorial” trees.”
Combinatorial Stochastic Processes (2006, methodology): “These ideas are applied and further developed in [120, 121, 142, 143].”