A functional limit theorem for the profile of search trees
| dc.creator | Drmota, Michael | |
| dc.creator | Janson, Svante | |
| dc.creator | Neininger, Ralph | |
| dc.date | 2006-09-14 | |
| dc.date | 2008-01-22 | |
| dc.date.accessioned | 2026-07-07T08:56:35Z | |
| dc.date.available | 2026-07-07T08:56:35Z | |
| dc.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. | |
| dc.description | 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) | |
| dc.identifier | https://arxiv.org/abs/math/0609385 | |
| dc.identifier | http://arxiv.org/abs/math/0609385 | |
| dc.identifier | Annals of Applied Probability 2008, Vol. 18, No. 1, 288-333 | |
| dc.identifier | doi:10.1214/07-AAP457 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/146662 | |
| dc.subject | Probability | |
| dc.subject | 60F17 (Primary); 68Q25, 68P10, 60C05 (Secondary) | |
| dc.title | A functional limit theorem for the profile of search trees | |
| dc.type | text |