Cecilia Holmgren: Stein's method to show limit laws for fringe trees

Quicksort is the most used of all sorting algorithms, since it is both
fast and simple. It can be represented by the binary search tree, a
certain type of random tree. The random recursive tree is another
extensively studied random tree. We have examined fringe trees ("small"
subtrees) in these two types of random trees.

By using a representation of Devroye, 2003, for the binary search tree,
and a bijection between recursive trees and binary trees, we use
different applications of Stein's method to show both new general
results on the asymptotic distributions for random variables on fringe
trees, as well as provide more direct proofs of several earlier results
in the field. The use of certain couplings related to Stein's method
(introduced by Barbour, Janson and Holst, 1992) leads to simple proofs
that the number of fringe trees of size k, k < n, where k tends to
infinity, in the binary search tree and the random recursive tree of
total size n, converges to a Poisson distribution.

Furthermore, combining these results and another version of Stein's
method, we can also show that for k=o(sqrt{n}) the number of fringe
trees in both types of random trees converges to a normal distribution.
The general results on fringe trees also lead to simple proofs of a
broad range of problems relating to random trees; one such example is
the asymptotic distribution of the number of protected nodes in the
binary search tree.

(Joint work with Svante Janson.)