Regenerative tree growth: binary self-similar continuum random trees and Poisson-Dirichlet compositions. (English) Zbl 1189.60162

Pitman, Jim; Winkel, Matthias

Ann. Probab. 37, No. 5, 1999-2041 (2009).

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 B. Haas, G. Miermont, J. Pitman and 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.

Reviewer: Heinrich Hering (Rockenberg)

MSC:

60J80

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

Keywords:

regenerative composition; Poisson-Dirichlet composition; Chinese restaurant process; Markov branching model; self-similar fragmentation; continuum random tree; \(\mathbb R\)-tree; recursive random tree; phylogenetic tree

Citations:

Zbl 1155.92033

References:

[1]	Aldous, D. (1991). The continuum random tree. I. Ann. Probab. 19 1-28. · Zbl 0722.60013
[2]	Aldous, D. (1996). Probability distributions on cladograms. In Random Discrete Structures ( Minneapolis , MN , 1993). IMA Vol. Math. Appl. 76 1-18. Springer, New York. · Zbl 0841.92015
[3]	Bertoin, J. (2002). Self-similar fragmentations. Ann. Inst. H. Poincaré Probab. Statist. 38 319-340. · Zbl 1002.60072
[4]	Bertoin, J. and Rouault, A. (2005). Discretization methods for homogeneous fragmentations. J. London Math. Soc. (2) 72 91-109. · Zbl 1077.60053
[5]	Blei, D. M., Griffiths, T. L. and Jordan, M. I. (2008). The nested Chinese restaurant process and hierarchical topic models. Preprint. Available at · Zbl 1327.68187
[6]	Dong, R., Goldschmidt, C. and Martin, J. B. (2006). Coagulation-fragmentation duality, Poisson-Dirichlet distributions and random recursive trees. Ann. Appl. Probab. 16 1733-1750. · Zbl 1123.60061
[7]	Duquesne, T. and Winkel, M. (2007). Growth of Lévy trees. Probab. Theory Related Fields 139 313-371. · Zbl 1126.60068
[8]	Evans, S. N., Pitman, J. and Winter, A. (2006). Rayleigh processes, real trees, and root growth with re-grafting. Probab. Theory Related Fields 134 81-126. · Zbl 1086.60050
[9]	Evans, S. N. and Winter, A. (2006). Subtree prune and regraft: A reversible real tree-valued Markov process. Ann. Probab. 34 918-961. · Zbl 1101.60054
[10]	Ford, D. J. (2005). Probabilities on cladograms: Introduction to the alpha model. Preprint. Available at
[11]	Gnedin, A. and Pitman, J. (2007). Exchangeable Gibbs partitions and Stirling triangles. Preprint. Available at · Zbl 1293.60010
[12]	Gnedin, A. and Pitman, J. (2005). Exchangeable Gibbs partitions and Stirling triangles. Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. ( POMI ) 325 83-102, 244-245. · Zbl 1293.60010
[13]	Gnedin, A. and Pitman, J. (2005). Regenerative composition structures. Ann. Probab. 33 445-479. · Zbl 1070.60034
[14]	Gnedin, A., Pitman, J. and Yor, M. (2006). Asymptotic laws for compositions derived from transformed subordinators. Ann. Probab. 34 468-492. · Zbl 1142.60327
[15]	Greenwood, P. and Pitman, J. (1980). Construction of local time and Poisson point processes from nested arrays. J. London Math. Soc. (2) 22 182-192. · Zbl 0427.60048
[16]	Greven, A., Pfaffelhuber, P. and Winter, A. (2009). Convergence in distribution of random metric measure spaces (\Lambda -coalescent measure trees). Probab. Theory Related Fields 145 285-322. · Zbl 1215.05161
[17]	Haas, B. and Miermont, G. (2004). The genealogy of self-similar fragmentations with negative index as a continuum random tree. Electron. J. Probab. 9 57-97 (electronic). · Zbl 1064.60076
[18]	Haas, B., Miermont, G., Pitman, J. and Winkel, M. (2008). Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic models. Ann. Probab. 36 1790-1837. · Zbl 1155.92033
[19]	Haas, B., Pitman, J. and Winkel, M. (2007). Spinal partitions and invariance under re-rooting of continuum random trees. Ann. Probab. Preprint. Available at · Zbl 1181.60128
[20]	Lamperti, J. (1972). Semi-stable Markov processes. I. Z. Wahrsch. Verw. Gebiete 22 205-225. · Zbl 0274.60052
[21]	Marchal, P. (2003). Constructing a sequence of random walks strongly converging to Brownian motion. In Discrete Random Walks ( Paris , 2003). Discrete Math. Theor. Comput. Sci. Proc. , AC 181-190 (electronic). Assoc. Discrete Math. Theor. Comput. Sci., Nancy. · Zbl 1034.60049
[22]	Mauldin, R. D., Sudderth, W. D. and Williams, S. C. (1992). Pólya trees and random distributions. Ann. Statist. 20 1203-1221. · Zbl 0765.62006
[23]	Pitman, J. (1997). Partition structures derived from Brownian motion and stable subordinators. Bernoulli 3 79-96. · Zbl 0882.60081
[24]	Pitman, J. (2006). Combinatorial Stochastic Processes. Lecture Notes in Math. 1875 . Springer, Berlin. · Zbl 1103.60004
[25]	Rémy, J.-L. (1985). Un procédé itératif de dénombrement d’arbres binaires et son application à leur génération aléatoire. RAIRO Inform. Théor. 19 179-195. · Zbl 0565.05037