Scaling limits of $k$-ary growing trees

Haas, Bénédicte; Stephenson, Robin

Annales de l'I.H.P. Probabilités et statistiques, Tome 51 (2015) no. 4, pp. 1314-1341.

Pour chaque entier $k\ge 2$, on introduit une suite d’arbres discrets $k$-aires construite récursivement en choisissant à chaque étape une arête uniformément parmi les arêtes de l’arbre pré-existant et greffant sur son « milieu » $k-1$ nouvelles arêtes. Lorsque $k=2$, cette procédure correspond à un algorithme introduit par Rémy. Pour chaque entier $k\ge 2$, nous décrivons la limite d’échelle de ces arbres lorsque le nombre d’étapes $n$ tend vers l’infini : ils grandissent à la vitesse $n^{1/k}$ vers un arbre réel aléatoire $k$-aire qui appartient à la famille des arbres de fragmentation auto-similaires. Cette convergence a lieu en probabilité, pour la topologie de Gromov–Hausdorff–Prokhorov. Nous étudions également l’emboîtement des arbres limites quand $k$ varie.

For each integer $k\ge 2$, we introduce a sequence of $k$-ary discrete trees constructed recursively by choosing at each step an edge uniformly among the present edges and grafting on “its middle” $k-1$ new edges. When $k=2$, this corresponds to a well-known algorithm which was first introduced by Rémy. Our main result concerns the asymptotic behavior of these trees as the number of steps $n$ of the algorithm becomes large: for all $k$, the sequence of $k$-ary trees grows at speed $n^{1/k}$ towards a $k$-ary random real tree that belongs to the family of self-similar fragmentation trees. This convergence is proved with respect to the Gromov–Hausdorff–Prokhorov topology. We also study embeddings of the limiting trees when $k$ varies.

[1] R. Abraham, J.-F. Delmas and P. Hoscheit. A note on the Gromov–Hausdorff–Prokhorov distance between (locally) compact metric measure spaces. Electron. J. Probab. 18 (14) (2013) 1–21. | MR | Zbl

[2] D. Aldous. The continuum random tree. II. An overview. In Stochastic Analysis (Durham, 1990). London Math. Soc. Lecture Note Ser. 167 23–70. Cambridge Univ. Press, Cambridge, 1991. | MR | Zbl

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

[4] E. Artin. The Gamma Function. Athena Series: Selected Topics in Mathematics. Holt, Rinehart and Winston, New York, 1964. Translated by Michael Butler. | MR | Zbl

[5] J. Bertoin. Homogeneous fragmentation processes. Probab. Theory Related Fields 121 (2001) 301–318. | DOI | MR | Zbl

[6] J. Bertoin. Self-similar fragmentations. Ann. Inst. Henri Poincaré Probab. Stat. 38 (3) (2002) 319–340. | Numdam | MR | Zbl

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

[8] S. Bhamidi. Universal techniques to analyze preferential attachment trees: Global and local analysis. Preprint, 2007.

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

[10] N. Curien and B. Haas. The stable trees are nested. Probab. Theory Related Fields 157 (1) (2013) 847–883. | MR | Zbl

[11] T. Duquesne and J.-F. Le Gall. Random trees, Lévy processes and spatial branching processes. Astérisque 281, vi+147 (2002). | Numdam | MR | Zbl

[12] T. Duquesne and J.-F. Le Gall. Probabilistic and fractal aspects of Lévy trees. Probab. Theory Related Fields 131 (4) (2005) 553–603. | MR | Zbl

[13] S. Evans, J. Pitman and A. Winter. Rayleigh processes, real trees, and root growth with re-grafting. Probab. Theory Related Fields 134 (1) (2006) 918–961. | MR | Zbl

[14] S. N. Evans. Probability and Real Trees. Lecture Notes in Mathematics 1920. Springer, Berlin, 2008. Lectures from the 35th Summer School on Probability Theory held in Saint-Flour, July 6–23, 2005. | MR | Zbl

[15] D. Ford. Probabilities on cladograms: Introduction to the alpha model. Ph.D. thesis, Stanford Univ., ProQuest LLC, Ann Arbor, MI, 2006. Available at arXiv:math/0511246. | MR

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

[17] B. Haas and G. Miermont. Self-similar scaling limits of non-increasing Markov chains. Bernoulli 17 (4) (2011) 1217–1247. | MR | Zbl

[18] B. Haas and G. Miermont. Scaling limits of Markov branching trees with applications to Galton–Watson and random unordered trees. Ann. Probab. 40 (6) (2012) 2589–2666. | MR | Zbl

[19] 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

[20] 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

[21] O. Kallenberg. Foundations of Modern Probability. Springer, Berlin, 2002. | DOI | MR | Zbl

[22] J.-F. Le Gall. Random real trees. Ann. Fac. Sci. Toulouse Math. (6) 15 (1) (2006) 35–62. | Numdam | MR | Zbl

[23] J.-F. Le Gall and Y. Le Jan. Branching processes in Lévy processes: The exploration process. Ann. Probab. 26 (1) (1998) 213–252. | MR | Zbl

[24] P. Marchal. 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, 2003. | MR | Zbl

[25] P. Marchal. A note on the fragmentation of a stable tree. In Fifth Colloquium on Mathematics and Computer Science. Discrete Math. Theor. Comput. Sci. Proc., AI 489–499. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2008. | MR | Zbl

[26] 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. With a foreword by Jean Picard. | MR | Zbl

[27] J. Pitman and M. Yor. The two-parameter Poisson–Dirichlet distribution derived from a stable subordinator. Ann. Probab. 25 (2) (1997) 855–900. | MR | Zbl

[28] J.-L. Rémy. 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 (2) (1985) 179–195. | Numdam | MR | Zbl

[29] A. Rudas, B. Tóth and B. Valkó. Random trees and general branching processes. Random Structures Algorithms 31 (2) (2007) 186–202. | MR | Zbl

[30] R. T. Smythe and H. M. Mahmoud. A survey of recursive trees. Teor. Ĭmovīr. Mat. Stat. 51 (1994) 1–29. | MR | Zbl

[31] R. Stephenson. General fragmentation trees. Electron. J. Probab. 18 (101) (2013) 1–45. | MR | Zbl

[32] R. Stephenson. Divers aspects des arbres aléatoires: Des arbres de fragmentation aux cartes planaires infinies. Ph.D. thesis, Univ. Paris-Dauphine, 2014. Available at www.normalesup.org/~stephens/thesis.pdf.