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

Abstract (VO)

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.

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.

Détail

DOI : 10.1214/14-AIHP622

Keywords: random growing trees, scaling limits, self-similar fragmentation trees, Gromov–Hausdorff–Prokhorov topology