On the asymptotic internal path length and the asymptotic Wiener index of random split trees

  • 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.

Download full text files

Export metadata

Metadaten
Author:Götz Olaf Munsonius
URN:urn:nbn:de:hebis:30:3-328939
DOI:https://doi.org/10.1214/EJP.v16-889
ISSN:1083-6489
ArXiv Id:http://arxiv.org/abs/1101.2570
Parent Title (English):Electronic journal of probability
Publisher:EMIS ELibEMS
Place of publication:[Madralin]
Document Type:Article
Language:English
Year of Completion:2014
Date of first Publication:2011/06/01
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Release Date:2014/01/29
Tag:Wiener index; internal path length; probabilistic analysis of algorithms; random trees
Volume:16
Page Number:28
First Page:1020
Last Page:1047
Note:
This work is licensed under a Creative Commons Attribution 3.0 License http://creativecommons.org/licenses/by/3.0/ .
HeBIS-PPN:363705619
Institutes:Informatik und Mathematik / Mathematik
Dewey Decimal Classification:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C05 Trees
60-XX PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX) / 60Fxx Limit theorems [See also 28Dxx, 60B12] / 60F05 Central limit and other weak theorems
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section {04 in that areag 68-00 General reference works (handbooks, dictionaries, bibliographies, etc.) / 68Pxx Theory of data / 68P05 Data structures
Sammlungen:Universitätspublikationen
Licence (German):License LogoCreative Commons - Namensnennung 3.0

OPUS4 Logo