60F05 Central limit and other weak theorems
Refine
Year of publication
- 2011 (2)
Document Type
- Article (2)
Language
- English (2)
Has Fulltext
- yes (2)
Is part of the Bibliography
- no (2)
Keywords
- Wiener index (1)
- coalescent (1)
- external branch (1)
- internal path length (1)
- probabilistic analysis of algorithms (1)
- random trees (1)
- reversibility (1)
- urn model (1)
Institute
- Mathematik (2)
In this paper we prove asymptotic normality of the total length of external branches in Kingman's coalescent. The proof uses an embedded Markov chain, which can be described as follows: Take an urn with n black balls. Empty it in n steps according to the rule: In each step remove a randomly chosen pair of balls and replace it by one red ball. Finally remove the last remaining ball. Then the numbers Uk, 0 < k < n, of red balls after k steps exhibit an unexpected property: (U0, ... ,Un) and (Un, ... ;U0) are equal in distribution.
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.