Séminaire du .. avril 2009, 14h00: Cecilia
Holmgren, Uppsala University.

*Random Records and Cuttings in Split Trees.*

I will discuss the number of random records in an arbitrary split tree
with * n * vertices (or equivalently,
the number of random cuttings required to eliminate the tree). I will
explain how a classical limit theorem for 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 my earlier results for the random binary
search tree, which is one specific case of split trees. Other
important
examples of split trees include *m*-ary search trees,
quadtrees, medians
of *(2k+1)*-trees, simplex trees, tries and digital search
trees.

Virginie Collette
Last modified: Mon Mar 30 14:53:58 CEST 2009