Restricted exchangeable partitions and embedding of associated hierarchies in continuum random trees
Annales de l'I.H.P. Probabilités et statistiques, Volume 49 (2013) no. 3, p. 839-872

We introduce the notion of a restricted exchangeable partition of . 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.

Nous introduisons la notion d’une partition restreinte échangeable de . 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.

DOI : https://doi.org/10.1214/12-AIHP533
Classification:  60G09,  60J80
Keywords: exchangeability, hierarchy, coalescent, fragmentation, continuum random tree, renewal theory
@article{AIHPB_2013__49_3_839_0,
     author = {Chen, Bo and Winkel, Matthias},
     title = {Restricted exchangeable partitions and embedding of associated hierarchies in continuum random trees},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     publisher = {Gauthier-Villars},
     volume = {49},
     number = {3},
     year = {2013},
     pages = {839-872},
     doi = {10.1214/12-AIHP533},
     zbl = {1283.60065},
     mrnumber = {3112436},
     language = {en},
     url = {http://www.numdam.org/item/AIHPB_2013__49_3_839_0}
}
Chen, Bo; Winkel, Matthias. Restricted exchangeable partitions and embedding of associated hierarchies in continuum random trees. Annales de l'I.H.P. Probabilités et statistiques, Volume 49 (2013) no. 3, pp. 839-872. doi : 10.1214/12-AIHP533. http://www.numdam.org/item/AIHPB_2013__49_3_839_0/

[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 883646 | Zbl 0562.60042

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

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

[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 1395604 | Zbl 0841.92015

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

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

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

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

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

[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 2480547 | Zbl 1190.60081

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

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

[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 2509650 | Zbl 1195.60016

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

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

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

[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 2041829 | Zbl 1064.60076

[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 2440924 | Zbl 1155.92033

[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 2546748 | Zbl 1181.60128

[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 1015698 | Zbl 0747.46045

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

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

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

[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 2018924 | Zbl 1042.60043

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

[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 2245368 | Zbl 1103.60004

[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 2561439 | Zbl 1189.60162

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

[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 1676282 | Zbl 0978.05002

[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 639197 | Zbl 0507.20006