Restricted exchangeable partitions and embedding of associated hierarchies in continuum random trees

Chen, Bo; Winkel, Matthias

Annales de l'I.H.P. Probabilités et statistiques, Tome 49 (2013) no. 3, pp. 839-872.

Nous introduisons la notion d’une partition restreinte échangeable de $\mathbb{N}$. Nous obtenons des représentations intégrales, nous considérons les fragmentations associées, des plongements dans des arbres aléatoires continus et la convergence vers de tels arbres limites. En particulier, nous déduisons de la théorie générale développée içi un résultat limite formulé en conjecture dans un travail précédent. Ce résultat particulier concerne les arbres alpha de Ford et leurs généralisations, les arbres alpha-gamma, deux exemples où l’échangeabilité restreinte arrive de manière naturelle.

We introduce the notion of a restricted exchangeable partition of $\mathbb{N}$. We obtain integral representations, consider associated fragmentations, embeddings into continuum random trees and convergence to such limit trees. In particular, we deduce from the general theory developed here a limit result conjectured previously for Ford’s alpha model and its extension, the alpha-gamma model, where restricted exchangeability arises naturally.

[1] D. Aldous. Exchangeability and related topics. In Lectures on Probability Theory and Statistics (Saint-Flour, 1983) 1-198. Lecture Notes in Math. 1117. Springer, Berlin, 1985. | MR | Zbl

[2] D. Aldous. The continuum random tree. I. Ann. Probab. 19(1) (1991) 1-28. | MR | Zbl

[3] D. Aldous. The continuum random tree. III. Ann. Probab. 21(1) (1993) 248-289. | MR | Zbl

[4] D. Aldous. Probability distributions on cladograms. In Random Discrete Structures (Minneapolis, MN, 1993) 1-18. IMA Vol. Math. Appl. 76. Springer, New York, 1996. | MR | Zbl

[5] J. Bertoin. Lévy Processes. Cambridge Tracts in Mathematics 121. Cambridge Univ. Press, Cambridge, 1996. | MR | Zbl

[6] J. Bertoin. Homogeneous fragmentation processes. Probab. Theory Related Fields 121(3) (2001) 301-318. | MR | Zbl

[7] J. Bertoin. The asymptotic behavior of fragmentation processes. J. Euro. Math. Soc. 5 (2003) 395-416. | MR | Zbl

[8] J. Bertoin. Random Fragmentation and Coagulation Processes. Cambridge Studies in Advanced Mathematics 102. Cambridge Univ. Press, Cambridge, 2006. | MR | Zbl

[9] J. Bertoin and A. Rouault. Discretization methods for homogeneous fragmentations. J. London Math. Soc. (2) 72(1) (2005) 91-109. | MR | Zbl

[10] B. Chen, D. Ford and M. Winkel. A new family of Markov branching trees: The alpha-gamma model. Electron. J. Probab. 14(15) (2009) 400-430 (electronic). | MR | Zbl

[11] R. Durrett. Probability: Theory and Examples, 2nd edition. Duxbury Press, Belmont, CA, 1996. | MR | Zbl

[12] D. J. Ford. Probabilities on cladograms: Introduction to the alpha model. Preprint, 2005. Available at arXiv:math/0511246v1. | MR

[13] A. Gnedin. Constrained exchangeable partitions. In Fourth Colloquium on Mathematics and Computer Science, Vol. AG 391-398. Discrete Mathematics and Theoretical Computer Science, Nancy, 2006. | MR | Zbl

[14] A. Gnedin, J. Pitman and M. Yor. Asymptotic laws for compositions derived from transformed subordinators. Ann. Probab. 34(2) (2006) 468-492. | MR | Zbl

[15] A. Gut. On the moments and limit distributions of some first passage times. Ann. Probab. 2 (1974) 277-308. | MR | Zbl

[16] B. Haas. Loss of mass in deterministic and random fragmentations. Stochastic Process. Appl. 106(2) (2003) 245-277. | MR | Zbl

[17] B. Haas and G. Miermont. The genealogy of self-similar fragmentations with negative index as a continuum random tree. Electron. J. Probab. 9(4) (2004) 57-97 (electronic). | MR | Zbl

[18] B. Haas, G. Miermont, J. Pitman and M. Winkel. Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic models. Ann. Probab. 36(5) (2008) 1790-1837. | MR | Zbl

[19] B. Haas, J. Pitman and M. Winkel. Spinal partitions and invariance under re-rooting of continuum random trees. Ann. Probab. 37(4) (2009) 1381-1411. | MR | Zbl

[20] C. Haulk and J. Pitman. A representation of exchangeable hierarchies by sampling from real trees. Preprint, 2011. Available at arXiv:1101.5619v1.

[21] S. V. Kerov. Combinatorial examples in the theory of AF-algebras. Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 172(Differentsialnaya Geom. Gruppy Li i Mekh. Vol. 10) (1989) 55-67, 169-170. | MR | Zbl

[22] J. F. C. Kingman. The representation of partition structures. J. London Math. Soc. (2) 18(2) (1978) 374-380. | MR | Zbl

[23] J. F. C. Kingman. Poisson Processes. Oxford Studies in Probability 3. Oxford Univ. Press, New York, 1993. | MR | Zbl

[24] P. Mccullagh, J. Pitman and M. Winkel. Gibbs fragmentation trees. Bernoulli 14(4) (2008) 988-1002. | MR | Zbl

[25] G. Miermont. Self-similar fragmentations derived from the stable tree. I. Splitting at heights. Probab. Theory Related Fields 127(3) (2003) 423-454. | MR | Zbl

[26] J. Pitman. Exchangeable and partially exchangeable random partitions. Probab. Theory Related Fields 102(2) (1995) 145-158. | MR | Zbl

[27] J. Pitman. Combinatorial Stochastic Processes. Lecture Notes in Mathematics 1875. Springer, Berlin, 2006. Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7-24, 2002. | MR | Zbl

[28] J. Pitman and M. Winkel. Regenerative tree growth: Binary self-similar continuum random trees and Poisson-Dirichlet compositions. Ann. Probab. 37(5) (2009) 1999-2041. | MR | Zbl

[29] E. Schroeder. Vier combinatorische Probleme. Z. f. Math. Phys. 15 (1870) 361-376. | JFM

[30] R. P. Stanley. Enumerative Combinatorics, Vol. 2. Cambridge Studies in Advanced Mathematics 62. Cambridge Univ. Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and Appendix 1 by Sergey Fomin. | MR | Zbl

[31] A. M. Vershik and S. V. Kerov. Asymptotic theory of the characters of a symmetric group. Funktsional. Anal. i Prilozhen. 15(4) (1981) 15-27, 96. | MR | Zbl