A functional limit theorem for the profile of search trees

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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α\log n\rfloor$ in a certain range of $α$. 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.
Published in at http://dx.doi.org/10.1214/07-AAP457 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Keywords

Probability, 60F17 (Primary); 68Q25, 68P10, 60C05 (Secondary)

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/146662

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0609385
 http://arxiv.org/abs/math/0609385
 Annals of Applied Probability 2008, Vol. 18, No. 1, 288-333
 doi:10.1214/07-AAP457

Collections

arXiv