Distances in $m$-ary recursive trees

Source abstract

We introduce the $m$-ary recursive tree, a tree structure that starts with a single node. At each step of the growth process, a random node, called the recruiter, is selected, and $m$ new nodes are attached to this recruiter. The main objective is an asymptotic analysis of distances in this structure. We first derive the distribution of the depth of nodes in such a tree as a convolution of independent (though not identically distributed) Bernoulli random variables. This representation yields normal and Poisson approximations with quantified errors for the depth. We also investigate the height of these trees, that is, the longest root-to-leaf distance, via a coupling to a weighted random recursive tree with suitably chosen weights. The coupling transfers the results on a strong law and tightness from the weighted recursive tree to the $m$-ary recursive tree. Furthermore, we establish a bivariate limit law for the Wiener index, that is, the sum of all pairwise distances, and the internal path length, that is, the sum of the depths of all nodes, using the contraction method. As a novel technical feature of our approach, we employ weighted norms instead of Euclidean norms within the contraction method.