TY  - JOUR
A1  - Munsonius, Götz Olaf
T1  - On the asymptotic internal path length and the asymptotic Wiener index of random split trees
T2  - Electronic journal of probability
N2  - The random split tree introduced by Devroye (1999) is considered. We derive a second order expansion for the mean of its internal path length and furthermore obtain a limit law by the contraction method. As an assumption we need the splitter having a Lebesgue density and mass in every neighborhood of 1. We use properly stopped homogeneous Markov chains, for which limit results in total variation distance as well as renewal theory are used. Furthermore, we extend this method to obtain the corresponding results for the Wiener index.
KW  - random trees
KW  - probabilistic analysis of algorithms
KW  - internal path length
KW  - Wiener index
Y1  - 2011
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/32893
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30:3-328939
SN  - 1083-6489
N1  - This work is licensed under a Creative Commons Attribution 3.0 License http://creativecommons.org/licenses/by/3.0/ .
VL  - 16
SP  - 1020
EP  - 1047
PB  - EMIS ELibEMS
CY  - [Madralin]
ER  -