Spinal partitions and invariance under re-rooting of continuum random trees

Abstract

We develop some theory of spinal decompositions of discrete and continuous fragmentation trees. Specifically, we consider a coarse and a fine spinal integer partition derived from spinal tree decompositions. We prove that for a two-parameter Poisson--Dirichlet family of continuous fragmentation trees, including the stable trees of Duquesne and Le Gall, the fine partition is obtained from the coarse one by shattering each of its parts independently, according to the same law. As a second application of spinal decompositions, we prove that among the continuous fragmentation trees, stable trees are the only ones whose distribution is invariant under uniform re-rooting.

Published in at http://dx.doi.org/10.1214/08-AOP434 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (8)

• Self-similar fragmentations derived from the stable tree II: splitting at nodes
• Asymptotic laws for compositions derived from transformed subordinators
• Subtree prune and regraft: a reversible real tree-valued Markov process
• Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic models
• Self-similar fragmentations derived from the stable tree I: splitting at heights
• Discretization methods for homogeneous fragmentations
• Probabilities on cladograms: introduction to the alpha model
• Ruelle's probability cascades seen as a fragmentation process

Cited by in corpus (24)

• Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees
• Lamperti-type laws
• Gibbs fragmentation trees
• Self-similar scaling limits of non-increasing Markov chains
• Regenerative tree growth: Binary self-similar continuum random trees and Poisson--Dirichlet compositions
• Regenerative tree growth: Markovian embedding of fragmenters, bifurcators, and bead splitting processes
• The structure of typical clusters in large sparse random configurations
• Generalized Mittag Leffler distributions arising as limits in preferential attachment models
• A representation of exchangeable hierarchies by sampling from real trees
• Interval partition evolutions with emigration related to the Aldous diffusion
• The falling appart of the tagged fragment and the asymptotic disintegration of the Brownian height fragmentation
• Mass-structure of weighted real trees
• Infinite stable looptrees
• Characterizations of exchangeable partitions and random discrete distributions by deletion properties
• Two-sided immigration, emigration and symmetry properties of self-similar interval partition evolutions
• A new family of Markov branching trees: the alpha-gamma model
• Regenerative tree growth: structural results and convergence
• A line-breaking construction of the stable trees
• Leaf-to-leaf distances in Catalan trees
• Restricted exchangeable partitions and embedding of associated hierarchies in continuum random trees
• A recursive distribution equation for the stable tree
• Gibbs Partitions, Riemann-Liouville Fractional Operators, Mittag-Leffler Functions, and Fragmentations Derived From Stable Subordinators
• The stable trees are nested
• Limiting Behavior Of Additive Functionals On The Stable Tree