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

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.


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


Zbl 1155.92033
Full Text: DOI arXiv


[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.