Subtree Sizes in Recursive Trees and Binary Search Trees: Berry–Esseen Bounds and Poisson Approximations
Subtree Sizes in Recursive Trees and Binary Search Trees: Berry–Esseen Bounds and Poisson Approximations
复制标题
递归树和二叉搜索树中的子树大小：Berry–Esseen 界限和泊松近似
DOI：
10.1017/s0963548308009243
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Michael Fuchs
中科院分区：
文献类型：
--
作者：
Michael Fuchs
我们研究了随机递归树和随机二叉搜索树的边缘上的子树的数量，其极限定律已知是正常的或泊松的或退化的，这取决于子树的大小。我们引入一个新的方法来解决这个问题，这有助于我们进一步澄清这一现象。更准确地说，我们得到最佳的Berry-Esseen界和局部极限定理的正常范围，并证明了泊松近似结果的子树大小趋于无穷大。
We study the number of subtrees on the fringe of random recursive trees and random binary search trees whose limit law is known to be either normal or Poisson or degenerate depending on the size of the subtree. We introduce a new approach to this problem which helps us to further clarify this phenomenon. More precisely, we derive optimal Berry–Esseen bounds and local limit theorems for the normal range and prove a Poisson approximation result as the subtree size tends to infinity.