Pour chaque entier , on introduit une suite d’arbres discrets -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 » nouvelles arêtes. Lorsque , cette procédure correspond à un algorithme introduit par Rémy. Pour chaque entier , nous décrivons la limite d’échelle de ces arbres lorsque le nombre d’étapes tend vers l’infini : ils grandissent à la vitesse vers un arbre réel aléatoire -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 varie.
For each integer , we introduce a sequence of -ary discrete trees constructed recursively by choosing at each step an edge uniformly among the present edges and grafting on “its middle” new edges. When , 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 of the algorithm becomes large: for all , the sequence of -ary trees grows at speed towards a -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 varies.
@article{AIHPB_2015__51_4_1314_0, author = {Haas, B\'en\'edicte and Stephenson, Robin}, title = {Scaling limits of $k$-ary growing trees}, journal = {Annales de l'I.H.P. Probabilit\'es et statistiques}, pages = {1314--1341}, publisher = {Gauthier-Villars}, volume = {51}, number = {4}, year = {2015}, doi = {10.1214/14-AIHP622}, mrnumber = {3414449}, zbl = {1329.60076}, language = {en}, url = {http://www.numdam.org/articles/10.1214/14-AIHP622/} }
TY - JOUR AU - Haas, Bénédicte AU - Stephenson, Robin TI - Scaling limits of $k$-ary growing trees JO - Annales de l'I.H.P. Probabilités et statistiques PY - 2015 SP - 1314 EP - 1341 VL - 51 IS - 4 PB - Gauthier-Villars UR - http://www.numdam.org/articles/10.1214/14-AIHP622/ DO - 10.1214/14-AIHP622 LA - en ID - AIHPB_2015__51_4_1314_0 ER -
%0 Journal Article %A Haas, Bénédicte %A Stephenson, Robin %T Scaling limits of $k$-ary growing trees %J Annales de l'I.H.P. Probabilités et statistiques %D 2015 %P 1314-1341 %V 51 %N 4 %I Gauthier-Villars %U http://www.numdam.org/articles/10.1214/14-AIHP622/ %R 10.1214/14-AIHP622 %G en %F AIHPB_2015__51_4_1314_0
Haas, Bénédicte; Stephenson, Robin. Scaling limits of $k$-ary growing trees. Annales de l'I.H.P. Probabilités et statistiques, Tome 51 (2015) no. 4, pp. 1314-1341. doi : 10.1214/14-AIHP622. http://www.numdam.org/articles/10.1214/14-AIHP622/
[1] A note on the Gromov–Hausdorff–Prokhorov distance between (locally) compact metric measure spaces. Electron. J. Probab. 18 (14) (2013) 1–21. | MR | Zbl
, and .[2] 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] The continuum random tree III. Ann. Probab. 21 (1) (1993) 248–289. | MR | Zbl
.[4] The Gamma Function. Athena Series: Selected Topics in Mathematics. Holt, Rinehart and Winston, New York, 1964. Translated by Michael Butler. | MR | Zbl
.[5] Homogeneous fragmentation processes. Probab. Theory Related Fields 121 (2001) 301–318. | DOI | MR | Zbl
.[6] Self-similar fragmentations. Ann. Inst. Henri Poincaré Probab. Stat. 38 (3) (2002) 319–340. | Numdam | MR | Zbl
.[7] Random Fragmentation and Coagulation Processes. Cambridge Studies in Advanced Mathematics 102. Cambridge Univ. Press, Cambridge, 2006. | DOI | MR | Zbl
.[8] Universal techniques to analyze preferential attachment trees: Global and local analysis. Preprint, 2007.
.[9] A new family of Markov branching trees: The alpha-gamma model. Electron. J. Probab. 14 (2009) 400–430. | DOI | MR | Zbl
, and .[10] The stable trees are nested. Probab. Theory Related Fields 157 (1) (2013) 847–883. | MR | Zbl
and .[11] Random trees, Lévy processes and spatial branching processes. Astérisque 281, vi+147 (2002). | Numdam | MR | Zbl
and .[12] Probabilistic and fractal aspects of Lévy trees. Probab. Theory Related Fields 131 (4) (2005) 553–603. | MR | Zbl
and .[13] Rayleigh processes, real trees, and root growth with re-grafting. Probab. Theory Related Fields 134 (1) (2006) 918–961. | MR | Zbl
, and .[14] 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] 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] 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
and .[17] Self-similar scaling limits of non-increasing Markov chains. Bernoulli 17 (4) (2011) 1217–1247. | MR | Zbl
and .[18] Scaling limits of Markov branching trees with applications to Galton–Watson and random unordered trees. Ann. Probab. 40 (6) (2012) 2589–2666. | MR | Zbl
and .[19] Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic models. Ann. Probab. 36 (5) (2008) 1790–1837. | MR | Zbl
, , and .[20] Spinal partitions and invariance under re-rooting of continuum random trees. Ann. Probab. 37 (4) (2009) 1381–1411. | MR | Zbl
, and .[21] Foundations of Modern Probability. Springer, Berlin, 2002. | DOI | MR | Zbl
.[22] Random real trees. Ann. Fac. Sci. Toulouse Math. (6) 15 (1) (2006) 35–62. | Numdam | MR | Zbl
.[23] Branching processes in Lévy processes: The exploration process. Ann. Probab. 26 (1) (1998) 213–252. | MR | Zbl
and .[24] 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] 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] 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] The two-parameter Poisson–Dirichlet distribution derived from a stable subordinator. Ann. Probab. 25 (2) (1997) 855–900. | MR | Zbl
and .[28] 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] Random trees and general branching processes. Random Structures Algorithms 31 (2) (2007) 186–202. | MR | Zbl
, and .[30] A survey of recursive trees. Teor. Ĭmovīr. Mat. Stat. 51 (1994) 1–29. | MR | Zbl
and .[31] General fragmentation trees. Electron. J. Probab. 18 (101) (2013) 1–45. | MR | Zbl
.[32] 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.
.Cité par Sources :