Asymptotics of heights in random trees constructed by aggregation

被引:5
作者
Haas, Benedicte [1 ]
机构
[1] Univ Paris 13, Sorbonne Paris Cite, LAGA, CNRS,UMR 7539, F-93430 Villetaneuse, France
关键词
random trees; line-breaking; uniform recursive trees; RANDOM RECURSIVE TREES;
D O I
10.1214/17-EJP31
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
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 [ 5, 10] 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) explodes. We determine the asymptotics of the height of T-n and of the subtrees of T-n spanned by the root and l points picked uniformly at random and independently in T-n, for all l is an element of IN.
引用
收藏
页数:25
相关论文
共 19 条
[1]   Critical random graphs: limiting constructions and distributional properties [J].
Addario-Berry, L. ;
Broutin, N. ;
Goldschmidt, C. .
ELECTRONIC JOURNAL OF PROBABILITY, 2010, 15 :741-775
[2]   THE CONTINUUM RANDOM TREE-III [J].
ALDOUS, D .
ANNALS OF PROBABILITY, 1993, 21 (01) :248-289
[3]  
Aldous D., 1991, London Math. Soc. Lecture Note Ser., V167, P23, DOI [10.1017/CBO9780511662980.003, DOI 10.1017/CBO9780511662980.003]
[4]  
Amini O., PROBAB THEO IN PRESS
[5]  
[Anonymous], 1999, CONVERGE PROBAB MEAS, DOI DOI 10.1002/9780470316962
[6]  
[Anonymous], 1989, ENCY MATH ITS APPL
[7]   On the asymptotic behaviour of random recursive trees in random environments [J].
Borovkov, K. A. ;
Vatutin, V. A. .
ADVANCES IN APPLIED PROBABILITY, 2006, 38 (04) :1047-1070
[8]   Large deviations for the weighted height of an extended class of trees [J].
Broutin, Nicolas ;
Devroye, Luc .
ALGORITHMICA, 2006, 46 (3-4) :271-297
[9]  
Curien N., ANN I FOURI IN PRESS
[10]   APPLICATIONS OF THE THEORY OF RECORDS IN THE STUDY OF RANDOM TREES [J].
DEVROYE, L .
ACTA INFORMATICA, 1988, 26 (1-2) :123-130