Asymptotic fringe distributions for general families of random trees. (English) Zbl 0733.60016

Aldous, David

Ann. Appl. Probab. 1, No. 2, 228-266 (1991).

From the author’s introduction: “We are concerned with local limit results which describe the shape of the tree near a typical vertex. Natural questions in any random tree model are: 1. What proportion of vertices are leaves? 2. What is the distribution of degrees of vertices? 3. What is the distribution of the size of the subtree rooted at a uniform vertex? 4. What is the distribution of the number of vertices within distance k of a uniform vertex? - These are the kind of functionals whose asymptotic behavior can be handled in our framework.”
The local limit theory presented in this paper can be applied to various families of random trees: rooted labelled trees, simply generated trees, binary search trees, recursive trees, tries, etc.

Reviewer: L.Mutafchiev (Sofia)

MSC:

60C05	Combinatorial probability
05C80	Random graphs (graph-theoretic aspects)

Keywords:

random tree model; local limit theory; binary search trees