A functional limit theorem for the profile of search trees

Details A functional limit theorem for the profile of search trees A functional limit theorem for the profile of search trees

2006-09-14

arxiv.org/abs/math/0609385v2

Annals of Applied Probability 2008, Vol. 18, No. 1, 288-333

Mathematics

Probability

Published in at http://dx.doi.org/10.1214/07-AAP457 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Inst

Scientific paper

10.1214/07-AAP457

We study the profile $X_{n,k}$ of random search trees including binary search trees and $m$-ary search trees. Our main result is a functional limit theorem of the normalized profile $X_{n,k}/\mathbb{E}X_{n,k}$ for $k=\lfloor\alpha\log n\rfloor$ in a certain range of $\alpha$. A central feature of the proof is the use of the contraction method to prove convergence in distribution of certain random analytic functions in a complex domain. This is based on a general theorem concerning the contraction method for random variables in an infinite-dimensional Hilbert space. As part of the proof, we show that the Zolotarev metric is complete for a Hilbert space.

Affiliated with

Also associated with

No associations

Rating

A functional limit theorem for the profile of search trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A functional limit theorem for the profile of search trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A functional limit theorem for the profile of search trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-537851