Change search
ReferencesLink to record
Permanent link

Direct link
Limit laws for functions of fringe trees for binary search trees and random recursive trees.
Stockholm University, Faculty of Science, Department of Mathematics.
Uppsala universitet, Sweden.
2015 (English)In: Electronic Journal of Probability, ISSN 1083-6489, Vol. 20, 4Article in journal (Refereed) Published
Abstract [en]

We prove general limit theorems for sums of functions of subtrees of (random) binary search trees and random recursive trees. The proofs use a new version of a representation by Devroye, and Stein's method for both normal and Poisson approximation together with certain couplings.As a consequence, we give simple new proofs of the fact that the number of fringe trees of size k=kn in the binary search tree or in the random recursive tree  (of total size n) has an asymptotical Poisson distribution if k→∞, and that the distribution is asymptotically normal for k=o(n√). Furthermore, we prove similar results for the number of subtrees of size k with some required property P, e.g., the number of copies of a certain fixed subtree T. Using the Cramér-Wold device, we show also that these random numbers for different fixed subtrees converge jointly to a multivariate normal distribution. We complete the paper by giving examples of applications of the general results, e.g., we obtain a normal limit law for the number of ℓ-protected nodes in a binary search tree or in a random recursive tree.

Place, publisher, year, edition, pages
2015. Vol. 20, 4
Keyword [en]
Fringe trees; Stein's method; Couplings; Limit laws; Binary search trees; Random recursive trees
National Category
URN: urn:nbn:se:su:diva-114312DOI: 10.1214/EJP.v20-3627ISI: 000350286000001OAI: diva2:791147
Available from: 2015-02-26 Created: 2015-02-26 Last updated: 2015-04-08Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Holmgren, Cecilia
By organisation
Department of Mathematics
In the same journal
Electronic Journal of Probability

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 42 hits
ReferencesLink to record
Permanent link

Direct link