Metadata
Abstract
We study the sizes of the Voronoi cells of uniformly chosen vertices in a random split tree of size . We prove that, for large, the largest of these Voronoi cells contains most of the vertices, while the sizes of the remaining ones are essentially all of order . 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 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 Voronoi cells is asymptotically uniformly distributed on the -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).
References
[AACFG18] 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 | Zbl
[ADMP17] Competing first passage percolation on random regular graphs, Random Struct. Algorithms, Volume 50 (2017) no. 4, pp. 534-583 | DOI | MR | Zbl
[BCH19] The fluctuations of the giant cluster for percolation on random split trees (2019) | arXiv
[BH12] The total path length of split trees, Ann. Appl. Probab., Volume 22 (2012) no. 5, pp. 1745-1777 | MR | Zbl
[BH21] The asymptotic distribution of cluster sizes for supercritical percolation on random split trees (2021) | arXiv
[BHK15] Fixed speed competition on the configuration model with infinite variance degrees: unequal speeds, Electron. J. Probab., Volume 20 (2015), 116 | MR | Zbl
[CDJH01] The profile of binary search trees, Ann. Appl. Probab., Volume 11 (2001) no. 4, pp. 1042-1062 | MR | Zbl
[Cha19] On tessellations of random maps and the -recurrence, Probab. Theory Relat. Fields, Volume 174 (2019) no. 1-2, pp. 477-500 | DOI | MR | Zbl
[Dev98] Universal limit laws for depths in random trees, SIAM J. Comput., Volume 28 (1998) no. 2, pp. 409-432 | DOI | MR | Zbl
[DG97] On the profile of random trees, Random Struct. Algorithms, Volume 10 (1997) no. 4, pp. 421-451 | DOI | MR | Zbl
[DH16] The winner takes it all, Ann. Appl. Probab., Volume 26 (2016) no. 4, pp. 2419-2453 | MR | Zbl
[GK54] Limit Distributions for Sums of Independent Random Variables, Addison-Wesley Publishing Group, 1954 | Zbl
[Gui17] On a conjecture by Chapuy about Voronoi cells in large maps, J. Stat. Mech. Theory Exp., Volume 2017 (2017) no. 10, 103401 | DOI | MR | Zbl
[Gut05] Probabiliy: a Graduate Course, Springer Texts in Statistics, Springer, 2005 | Zbl
[HJ17] Fringe trees, Crump–Mode–Jagers branching processes and -ary search trees, Probab. Surv., Volume 14 (2017), pp. 53-154 | MR | Zbl
[HK15] Fixed speed competition on the configuration model with infinite variance degrees: equal speeds (2015) | arXiv
[Hol12] Novel characteristics of split trees by use of renewal theory, Electron. J. Probab., Volume 17 (2012), 5 | MR | Zbl
[Jan19] Random recursive trees and preferential attachment trees are random split trees, Comb. Probab. Comput., Volume 28 (2019) no. 1, pp. 81-99 | DOI | MR | Zbl
[Kat05] Width of a scale-free tree, J. Appl. Probab., Volume 42 (2005) no. 3, pp. 839-850 | DOI | MR | Zbl
[MM17] Measure-valued Pólya processes, Electron. J. Probab., Volume 22 (2017), 26, p. 33 | Zbl