Voronoi cells in random split trees

Drewitz, Alexander; Heydenreich, Markus; Mailler, Cécile

Annales Henri Lebesgue, Tome 7 (2024), pp. 123-159

We study the sizes of the Voronoi cells of $k$ uniformly chosen vertices in a random split tree of size $n$. We prove that, for $n$ large, the largest of these $k$ Voronoi cells contains most of the vertices, while the sizes of the remaining ones are essentially all of order $nexp(-\mathrm{const}\sqrt{logn})$. This “winner-takes-all” phenomenon persists if we modify the definition of the Voronoi cells by (a) introducing random edge lengths (with suitable moment assumptions), and (b) assigning different “influence” parameters (called “speeds” in the paper) to each of the $k$ vertices. Our findings are in contrast to corresponding results on random uniform trees and on the continuum random tree, where it is known that the vector of the relative sizes of the $k$ Voronoi cells is asymptotically uniformly distributed on the $(k-1)$-dimensional simplex.

Two intermediary steps in the proof of our main result may be of independent interest because of the information they give on the typical shape of large random split trees: we prove convergence in probability of their “profile”, and we prove asymptotic results for the size of fringe trees (trees rooted at an ancestor of a uniform random node).

Dans ce papier, nous étudions la taille des cellules de Voronoï de $k$ nœuds choisis uniformément au hasard dans un arbre aléatoire de fragmentation de taille $n$. Nous montrons que, pour $n$ grand, la plus grande de ces $k$ cellules de Voronoï contient la plupart des nœuds de l’arbre, alors que les tailles des autre cellules sont d’ordre $nexp(-\mathrm{const}\sqrt{logn})$. Cet effet du “gagnant qui décroche la timbale” persiste si l’on modifie la définition des cellules de Voronoï (a) en introduisant des longueurs d’arêtes aléatoires (sous une hypothèse de moment appropriée), et (b) en attribuant différents paramètres d’“influence” (appelés “vitesses” dans le papier) aux $k$ différents nœuds choisis. Nos résultats sont à mettre en parallèle de ceux obtenus dans le cas d’un arbre aléatoire uniforme et dans le cas de l’arbre continu Brownien, pour lesquels il est connu que le vecteur des tailles relatives des $k$ cellules de Voronoï est asymptotiquement uniforme sur le simplexe de dimension $(k-1)$.

Deux étapes intermédiaires de notre preuve pourront être intéressantes en elles-mêmes pour les informations qu’elles donnent sur la forme typique d’un grand arbre aléatoire de fragmentation : la convergence en probabilité du profil de ces arbres, et un résultat asymptotique sur la taille de leurs arbres de frange (arbres enracinés en un ancêtre d’un nœud uniforme).

Classification : 05C80, 60C05
Keywords: Random split trees, Voronoi cells in graphs, competition processes, profile, fringe trees

[AACFG18] Addario-Berry, Louigi; Angel, Omer; Chapuy, Guillaume; Fusy, Éric; Goldschmidt, Christina Voronoi tessellations in the CRT and continuum random maps of finite excess, Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7–10, 2018, Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM), 2018, pp. 933-946 | MR | Zbl

[ADMP17] Antunović, Tonći; Dekel, Yael; Mossel, Elchanan; Peres, Yuval Competing first passage percolation on random regular graphs, Random Struct. Algorithms, Volume 50 (2017) no. 4, pp. 534-583 | DOI | MR | Zbl

[BCH19] Berzunza, Gabriel; Cai, Xing Shi; Holmgren, Cecilia The fluctuations of the giant cluster for percolation on random split trees (2019) | arXiv

[BH12] Broutin, Nicolas; Holmgren, Cecilia The total path length of split trees, Ann. Appl. Probab., Volume 22 (2012) no. 5, pp. 1745-1777 | Zbl | MR

[BH21] Berzunza, Gabriel; Holmgren, Cecilia The asymptotic distribution of cluster sizes for supercritical percolation on random split trees (2021) | arXiv

[BHK15] Baroni, Enrico; van der Hofstad, Remco; Komjáthy, Júlia Fixed speed competition on the configuration model with infinite variance degrees: unequal speeds, Electron. J. Probab., Volume 20 (2015), 116 | Zbl | MR

[CDJH01] Chauvin, Brigitte; Drmota, Michael; Jabbour-Hattab, Jean The profile of binary search trees, Ann. Appl. Probab., Volume 11 (2001) no. 4, pp. 1042-1062 | MR | Zbl

[Cha19] Chapuy, Guillaume On tessellations of random maps and the $t_g$-recurrence, Probab. Theory Relat. Fields, Volume 174 (2019) no. 1-2, pp. 477-500 | Zbl | DOI | MR

[Dev98] Devroye, Luc Universal limit laws for depths in random trees, SIAM J. Comput., Volume 28 (1998) no. 2, pp. 409-432 | Zbl | DOI | MR

[DG97] Drmota, Michael; Gittenberger, Bernhard On the profile of random trees, Random Struct. Algorithms, Volume 10 (1997) no. 4, pp. 421-451 | Zbl | DOI | MR

[DH16] Deijfen, Maria; Hofstad, Remco van der The winner takes it all, Ann. Appl. Probab., Volume 26 (2016) no. 4, pp. 2419-2453 | Zbl | MR

[GK54] Gnedenko, Boris V.; Kolmogorov, Andrei N. Limit Distributions for Sums of Independent Random Variables, Addison-Wesley Publishing Group, 1954 | MR | Zbl

[Gui17] Guitter, Emmanuel On a conjecture by Chapuy about Voronoi cells in large maps, J. Stat. Mech. Theory Exp., Volume 2017 (2017) no. 10, 103401 | Zbl | DOI | MR

[Gut05] Gut, Allan Probabiliy: a Graduate Course, Springer Texts in Statistics, Springer, 2005 | MR | Zbl

[HJ17] Holmgren, Cecilia; Janson, Svante Fringe trees, Crump–Mode–Jagers branching processes and $m$-ary search trees, Probab. Surv., Volume 14 (2017), pp. 53-154 | Zbl | MR

[HK15] van der Hofstad, Remco; Komjáthy, Júlia Fixed speed competition on the configuration model with infinite variance degrees: equal speeds (2015) | arXiv

[Hol12] Holmgren, Cecilia Novel characteristics of split trees by use of renewal theory, Electron. J. Probab., Volume 17 (2012), 5 | Zbl | MR

[Jan19] Janson, Svante Random recursive trees and preferential attachment trees are random split trees, Comb. Probab. Comput., Volume 28 (2019) no. 1, pp. 81-99 | Zbl | DOI | MR

[Kat05] Katona, Zsolt Width of a scale-free tree, J. Appl. Probab., Volume 42 (2005) no. 3, pp. 839-850 | Zbl | MR | DOI

[MM17] Mailler, Cécile; Marckert, Jean-François Measure-valued Pólya processes, Electron. J. Probab., Volume 22 (2017), 26, p. 33 | MR | Zbl