Distances in m-ary recursive trees
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.
Related
- Maximal Center of Distances of Finite Ultrametric Spaces and Perfect Binary Trees
- Total Path Length in Power-Weight Recursive Trees: Martingale Limits and Global Fluctuations
- Spawn Freely, Act Sparingly: Progressive Risk Vesting for Recursive LLM-Agent Trees
- Pinned distances of planar sets with low dimension
- A Reading of the Treatise of Aristarchus of Samos on the Sizes and Distances of the Sun and Moon
BibTeX
@misc{bhutani2026distances,
title = {{Distances in $m$-ary recursive trees}},
author = {Kiran Bhutani and Ravi Kalpathy and Florian Lesny and Hosam Mahmoud and Ralph Neininger},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.33636},
eprint = {2609.33636},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33636},
}
RIS
TY - UNPB
TI - Distances in m-ary recursive trees
AU - Kiran Bhutani
AU - Ravi Kalpathy
AU - Florian Lesny
AU - Hosam Mahmoud
AU - Ralph Neininger
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2609.33636
UR - https://arxiv.org/abs/2609.33636
AB - 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.
ER -