## 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.

### MSC:

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

Zbl 1155.92033
Full Text:

### References:

  Aldous, D. (1991). The continuum random tree. I. Ann. Probab. 19 1-28. · Zbl 0722.60013  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  Bertoin, J. (2002). Self-similar fragmentations. Ann. Inst. H. Poincaré Probab. Statist. 38 319-340. · Zbl 1002.60072  Bertoin, J. and Rouault, A. (2005). Discretization methods for homogeneous fragmentations. J. London Math. Soc. (2) 72 91-109. · Zbl 1077.60053  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  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  Duquesne, T. and Winkel, M. (2007). Growth of Lévy trees. Probab. Theory Related Fields 139 313-371. · Zbl 1126.60068  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  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  Ford, D. J. (2005). Probabilities on cladograms: Introduction to the alpha model. Preprint. Available at  Gnedin, A. and Pitman, J. (2007). Exchangeable Gibbs partitions and Stirling triangles. Preprint. Available at · Zbl 1293.60010  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  Gnedin, A. and Pitman, J. (2005). Regenerative composition structures. Ann. Probab. 33 445-479. · Zbl 1070.60034  Gnedin, A., Pitman, J. and Yor, M. (2006). Asymptotic laws for compositions derived from transformed subordinators. Ann. Probab. 34 468-492. · Zbl 1142.60327  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  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  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  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  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  Lamperti, J. (1972). Semi-stable Markov processes. I. Z. Wahrsch. Verw. Gebiete 22 205-225. · Zbl 0274.60052  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  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  Pitman, J. (1997). Partition structures derived from Brownian motion and stable subordinators. Bernoulli 3 79-96. · Zbl 0882.60081  Pitman, J. (2006). Combinatorial Stochastic Processes. Lecture Notes in Math. 1875 . Springer, Berlin. · Zbl 1103.60004  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.