Asymptotics of heights in random trees constructed by aggregation

2016/06/21 by Bénédicte Haas, Haas, Bénédicte
Mathematics · #FOS: Mathematics #Probability (math.PR) #math.PR

paper · pdf · doi:10.48550/arxiv.1606.06536

arxiv created 2016/06/21 · arxiv updated 2016/06/22

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₁ of length a₁. 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 ℓ ∈ \mathbb N.

Related

• Random trees constructed by aggregation
• Random trees have height O(√(n))
• On exponentially height-penalized random trees
• Diffusion limited aggregation on a tree
• Scaling limit of trees with vertices of fixed degrees and heights