Limit laws for sums of functions of subtrees of random binary search trees

摘要

We consider sums of functions of subtrees of a random binary search tree and obtain general laws of large numbers and central limit theorems. These sums correspond to random recurrences of the quicksort type, X-n (L) double under bar = X-In + Xn-1-In' + Y-n, n greater than or equal to 1, where I-n is uniformly distributed on {0, 1,..., n-1}, Y-n is a given random variable, X-k (L) double under bar X-k' for all k, and, given I-n, X-In and Xn-1-In' are independent. Conditions are derived such that (X-n - mun)/sigmarootn (L) over right arrow N(0,1), the normal distribution, for some finite constants mu and sigma. [References: 31]