Cecilia Holmgren: Stein's Method to Show Limit Laws for Fringe Trees

The binary search tree or Quicksort is the most used of all sorting algorithms, since it is both fast and simple. The random recursive tree is another extensively studied random tree. We have examined fringe trees in these two types of random trees. By using a representation of Devroye for the binary search tree, and a well-known 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 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.)