Using Stein's method to show Poisson and normal limit laws for fringe subtrees.
2014 (English)In: Discrete mathematics and theoretical computer science (Online), ISSN 1365-8050, Vol. Proc., no BA, 169-180 p.Article in journal (Refereed) Published
The use of Stein’s method and certain couplings allow provision of simple proofs showing that in both of these trees, the number of fringe subtrees of size k < n, where k ! 1, can be approximated by a Poisson distribution. Combining these results and another version of Stein’s method, we can also show that for k = o(pn), the number of fringe subtrees in both types of random trees has asymptotically a normal distribution as n ! 1. Furthermore, using the Cram´er–Wold device, we show that a random vector with components corresponding to the random number of copies of certain fixed fringe subtrees Ti, has asymptotically a multivariate normal distribution. We can then use these general results on fringe subtrees to obtain simple solutions to a broad range of problems relating to random trees; as an example, we can prove that the number of protected nodes in the binary search tree has asymptotically a normal distribution.
Place, publisher, year, edition, pages
2014. Vol. Proc., no BA, 169-180 p.
Fringe subtrees. Stein’s method, Couplings, Limit laws, Binary search trees, Recursive trees
IdentifiersURN: urn:nbn:se:su:diva-114311OAI: oai:DiVA.org:su-114311DiVA: diva2:791141