Voronoi cells in split trees with heavy-tailed split distribution

The aim of this project is to understand the Voronoi cells of k random nodes in a large random split tree with heavy-tailed split distribution. The case of a light-tailed distribution is treated by Drewitz, Heydendreich and Mailler (DHM) . The proof relies on understanding the profile of the random split tree in enough detail; in particular, DHM prove convergence in probability of the (renormalised) profile to a Gaussian. In the case of heavy-tailed distribution, we expect the profile to converge to a non-Gaussian limit, and after a normalisation of a different order to the light-tail case. This is because the proofs rely on the central limit theorem in the light-tail case, and will rely on limit theorem for sums of i.i.d. heavy-tailed random variables in the heavy-tailed case. The project includes adapting the lemma of Devroye for the height of a uniform node in a random split tree to trees with a heavy-tailed split ditribution. This will be done using the Generalised Central Limit Theorem. From this we will analyse the size of a subtree in a heavy-tailed random split tree.

There are exisiting results for Voronoi partitions in other contexts. Addario-Berry et al show that the Voronoi partition for uniform trees is a uniform vector on the simplex, whereas DHM show a winner takes all behaviour for random split trees. In particular one of the authors conjecture that this uniform limit is true for all random maps. This problem has been studied extensively on \mathbb R^d for Possion Voronoi tessellations yielding results for the volume and surface area of cells, amongst others.