Asymptotics of heights in random trees constructed by aggregation

Bénédicte Haas

paper

Asymptotics of heights in random trees constructed by aggregation

arXiv:1606.06536

Abstract

To each sequence $(a_{n})$ of positive real numbers we associate a growing sequence $(T_{n})$ of continuous trees built recursively by gluing at step $n$ a segment of length $a_{n}$ on a uniform point of the pre-existing tree, starting from a segment $T_{1}$ of length $a_{1}$ . Previous works on that model focus on the influence of $(a_{n})$ on the compactness and Hausdorff dimension of the limiting tree. Here we consider the cases where the sequence $(a_{n})$ is regularly varying with a non-negative index, so that the sequence $(T_{n})$ exploses. We determine the asymptotics of the height of $T_{n}$ and of the subtrees of $T_{n}$ spanned by the root and $ℓ$ points picked uniformly at random and independently in $T_{n}$ , for all $ℓ \in N$ .