Using Stein's method to show Poisson and normal limit laws for fringe subtrees

MaRDI QIDQ2789554zbMATH OpenFDO

Authors Cecilia Holmgren, Svante Janson

Publication date 1 March 2016

Full work available at URL https://hal.inria.fr/hal-01077251v2/document

zbMATH Keywords

Stein's methodlimit lawscouplingsbinary search treesrecursive treesfringe subtrees

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Central limit and other weak theorems (60F05) Data structures (68P05) Combinatorial probability (60C05)

Recommendations

• Limit laws for functions of fringe trees for binary search trees and random recursive trees
• Subtree Sizes in Recursive Trees and Binary Search Trees: Berry–Esseen Bounds and Poisson Approximations
• Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees
• Using Pólya urns to show normal limit laws for fringe subtrees in \(m\)-ary search trees
• On the subtrees of random binary search trees

Cited in

(6)

• A nonuniform bound to an independent test in high dimensional data analysis via Stein's method
• A non-uniform bound on Poisson approximation of the number of subtrees of size \(k\) in a random binary search tree \(T_n\)
• Limit laws for self-loops and multiple edges in the configuration model
• On 2-protected nodes in random digital trees
• Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees
• Subtree Sizes in Recursive Trees and Binary Search Trees: Berry–Esseen Bounds and Poisson Approximations

This page was built for publication: Using Stein's method to show Poisson and normal limit laws for fringe subtrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2789554)