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 $ kightarrowinfty $, and that the distribution is asymptotically normal for $ k=o(sqrt{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 $ ell $-protected nodes in a binary search tree or in a random recursive tree.
展开▼
机译：我们证明了（随机）二分搜索树和随机递归树的子树的函数和的一般极限定理。证明使用Devroye的新表示形式，并使用Stein的方法进行正态和泊松近似以及某些耦合，因此，我们给出了一个简单的新证明，即$ k = k_n大小的条纹树的数量如果$ k rightarrow infty $，则二叉查找树或随机递归树中的$具有渐近的Poisson分布，并且对于$ k = o（ sqrt { n}）$。此外，对于具有某些必需属性$ P $的大小为$ k $的子树数量，例如某个固定子树$ T $的副本数，我们证明了类似的结果。使用Cramér-Wold装置，我们还显示出这些用于不同固定子树的随机数共同收敛于多元正态分布。我们通过给出一般结果的应用示例来完善本文，例如，我们获得了二叉搜索树或随机递归树中受 ell $保护的节点数的正则极限定律。
展开▼
