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), p. 1314-1341 / Harvested from Numdam

Résumé

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.

Abstract

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.

Détail

Publié le : 2015-01-01

MR 3414449

DOI : https://doi.org/10.1214/14-AIHP622

Bibliographie

[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 3035742 | Zbl 1285.60004

[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 1166406 | Zbl 0791.60008

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

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

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

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

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

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

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

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

[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 2147221 | Zbl 1070.60076

[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 2221786 | Zbl 1086.60050

[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 2351587 | Zbl 1139.60006

[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 2708802

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

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

[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 3050512 | Zbl 1259.60033

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

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

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

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

[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 1617047 | Zbl 0948.60071

[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 2042386 | Zbl 1034.60049

[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 2508809

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

[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 1434129 | Zbl 0880.60076

[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 803997 | Zbl 0565.05037

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

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

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

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