Regenerative tree growth: binary self-similar continuum random trees and Poisson-Dirichlet compositions

DOI10.1214/08-AOP445MaRDI QIDQ1035868zbMATH OpenOpenAlexFDO

Authors Matthias Winkel, Jim Pitman

Publication date 4 November 2009

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

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

zbMATH Keywords

\(\mathbb R\)-treeChinese restaurant processcontinuum random treeMarkov branching modelphylogenetic treePoisson-Dirichlet compositionrecursive random treeregenerative compositionself-similar fragmentation

Mathematics Subject Classification ID

Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Abstract: We use a natural ordered extension of the Chinese Restaurant Process to grow a two-parameter family of binary self-similar continuum fragmentation trees. We provide an explicit embedding of Ford's sequence of alpha model trees in the continuum tree which we identified in a previous article as a distributional scaling limit of Ford's trees. In general, the Markov branching trees induced by the two-parameter growth rule are not sampling consistent, so the existence of compact limiting trees cannot be deduced from previous work on the sampling consistent case. We develop here a new approach to establish such limits, based on regenerative interval partitions and the urn-model description of sampling from Dirichlet random distributions.

Review text

Consider a stochastic binary tree growth process \(\{T_n; n\geq 1\}\), constructed according to the following \((\alpha,\theta)\)-selection rule: Let \(0\leq\alpha\leq 1\) and \(\theta\geq 0\). (i) For \(n\geq 2\), the tree \(T_n\) branches at the branch point adjacent to the root into two sub-trees \(T_{n,0}\) and \(T_{n,1}\). Given these are of sizes \(m\) and \(n-m\), say, where \(T_{n,1}\) contains the smallest label in \(T_n\), assign the weight a to the edge connecting the root and the adjacent branch point, weights \(m-\alpha\) and \(n-m-1+\theta\), respectively, to the sub-trees. (ii) Select the root edge or a sub-tree with probabilities proportional to these weights. If a sub-tree with two or more leaves was selected, recursively apply the weighting procedure (i) to the selected sub-tree, until the root edge or a sub-tree with a single leaf was selected. If a sub-tree with a single leaf was selected, select the unique edge of this sub-tree. The limit theory of \textit{B. Haas}, \textit{G. Miermont}, \textit{J. Pitman} and \textit{M. Winkel} [Ann. Probab. 36, No. 5, 1790--1837 (2008; Zbl 1155.92033)], covers the special case \(\alpha+\theta= 1\), but relies on sampling consistency: (Let \(T^0_n\) be obtained from \(T_n\) by removing the leaf labels, and \(T^0_n\) from \(T^0_{n-1}\) by removing a leaf chosen uniformly at random. \(\{T_n; n\geq 1\}\) is called weakly sampling consistent if the distributions of \(T^0_n\) and \(\widehat T^0_n\) coincide for all \(n\geq 1\).) In general, \((\alpha,\theta)\)-tree growth processes are not weakly sampling consistent. So, the authors now take a new approach to the existence of compact limiting trees, which applies to the general case. It is based on regenerative interval partitions and the urn-model description of sampling from Dirichlet random distributions.

Recommendations

• Regenerative tree growth: structural results and convergence
• Regenerative tree growth: Markovian embedding of fragmenters, bifurcators, and bead splitting processes
• Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic mod\-els
• The continuum random tree. III
• A new family of Markov branching trees: the alpha-gamma model

Cites work

• Asymptotic laws for compositions derived from transformed subordinators
• Coagulation-fragmentation duality, Poisson-Dirichlet distributions and random recursive trees
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• Construction of Local Time and Poisson Point Processes from Nested Arrays
• Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic mod\-els
• Convergence in distribution of random metric measure spaces (\(\Lambda \)-coalescent measure trees)
• DISCRETIZATION METHODS FOR HOMOGENEOUS FRAGMENTATIONS
• Growth of Lévy trees
• scientific article; zbMATH DE number 3900794 (Why is no real title available?)
• scientific article; zbMATH DE number 2046067 (Why is no real title available?)
• scientific article; zbMATH DE number 850224 (Why is no real title available?)
• scientific article; zbMATH DE number 2214054 (Why is no real title available?)
• Partition structures derived from Brownian motion and stable subordinators
• Polya trees and random distributions
• Rayleigh processes, real trees, and root growth with re-grafting
• Regenerative composition structures
• Self-similar fragmentations
• Semi-stable Markov processes. I
• Spinal partitions and invariance under re-rooting of continuum random trees
• Subtree prune and regraft: a reversible real tree-valued Markov process
• The continuum random tree. I
• The genealogy of self-similar fragmentations with negative index as a continuum random tree
• The nested Chinese restaurant process and Bayesian nonparametric inference of topic hierarchies

Cited in

(23)

• A representation of exchangeable hierarchies by sampling from random real trees
• Scaling limits for some random trees constructed inhomogeneously
• Recursive construction of continuum random trees
• ``Trees under attack: a Ray-Knight representation of Feller's branching diffusion with logistic growth
• Exchangeable hierarchies and mass-structure of weighted real trees
• Diffusions on a space of interval partitions: construction from marked Lévy processes
• Diffusions on a space of interval partitions: Poisson-Dirichlet stationary distributions
• A Ray-Knight representation of up-down Chinese restaurants
• The leftmost column of ordered Chinese restaurant process up-down chains: intertwining and convergence
• Diffusive limits of two-parameter ordered Chinese restaurant process up-down chains
• Restricted exchangeable partitions and embedding of associated hierarchies in continuum random trees
• Gibbs partitions, Riemann-Liouville fractional operators, Mittag-Leffler functions, and fragmentations derived from stable subordinators
• Branch merging on continuum trees with applications to regenerative tree growth
• Ranked masses in two-parameter Fleming–Viot diffusions
• A down‐up chain with persistent labels on multifurcating trees
• Two-sided immigration, emigration and symmetry properties of self-similar interval partition evolutions
• Diffusions on a space of interval partitions: the two-parameter model
• A binary embedding of the stable line-breaking construction
• Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees
• Up-down ordered Chinese restaurant processes with two-sided immigration, emigration and diffusion limits
• Regenerative tree growth: structural results and convergence
• Metrics on sets of interval partitions with diversity
• Regenerative tree growth: Markovian embedding of fragmenters, bifurcators, and bead splitting processes

This page was built for publication: Regenerative tree growth: binary self-similar continuum random trees and Poisson-Dirichlet compositions

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