In this paper we study the number of random records in an arbitrary split tree
(or, equivalently, the number of random cuttings required to eliminate the
tree). We show that a classical limit theorem for the convergence of sums of
triangular arrays to infinitely divisible distributions can be used to
determine the distribution of this number. After normalization the
distributions are shown to be asymptotically weakly 1-stable. This work is a
generalization of our earlier results for the random binary search tree in
Holmgren (2010), which is one specific case of split trees. Other important
examples of split trees include m-ary search trees, quad trees, medians
of (2k + 1)-trees, simplex trees, tries, and digital search trees.
@article{1300198517,
author = {Holmgren, Cecilia},
title = {A weakly 1-stable distribution for the number of random records and cuttings in split trees},
journal = {Adv. in Appl. Probab.},
volume = {43},
number = {1},
year = {2011},
pages = { 151-177},
language = {en},
url = {http://dml.mathdoc.fr/item/1300198517}
}
Holmgren, Cecilia. A weakly 1-stable distribution for the number of random records and cuttings in split trees. Adv. in Appl. Probab., Tome 43 (2011) no. 1, pp. 151-177. http://gdmltest.u-ga.fr/item/1300198517/