Change search
ReferencesLink to record
Permanent link

Direct link
Limit laws for functions of fringe trees for binary search trees and random recursive trees
Stockholms universitet.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.
2015 (English)In: Electronic Journal of Probability, ISSN 1083-6489, E-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 = k(n) in the binary search tree or in the random recursive tree (of total size n) has an asymptotical Poisson distribution if k -> infinity, and that the distribution is asymptotically normal for k = o(root 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 Cramer-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 l-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
Probability Theory and Statistics
URN: urn:nbn:se:uu:diva-248646DOI: 10.1214/EJP.v20-3627ISI: 000350286000001OAI: diva2:802290
Available from: 2015-04-12 Created: 2015-04-06 Last updated: 2016-02-17Bibliographically approved

Open Access in DiVA

fulltext(545 kB)74 downloads
File information
File name FULLTEXT01.pdfFile size 545 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Holmgren, CeciliaJanson, Svante
By organisation
Analysis and Probability Theory
In the same journal
Electronic Journal of Probability
Probability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar
Total: 74 downloads
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: 214 hits
ReferencesLink to record
Permanent link

Direct link