Second phase changes in random m-ary search trees and generalized quicksort: Convergence rates

• 成果类型: Article
• 署名作者: Hwang, HK
• 署名单位: Academia Sinica - Taiwan
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• 发表日期: 2003
• 页码: 609-629
• 关键词: recurrence

摘要

We study the convergence rate to normal limit law for the space requirement of random m-ary search trees. While it is known that the random variable is asymptotically normally distributed for 3 less than or equal to m less than or equal to 26 and that the limit law does not exist for m > 26, we show that the convergence rate is O(n(-1/2)) for 3 less than or equal to m less than or equal to 19 and is O(n(-3(3/2-alpha))), where 4/3 < alpha < 3/2 is a parameter depending on m for 20 less than or equal to m less than or equal to 26. Our approach is based on a refinement to the method of moments and applicable to other recursive random variables; we briefly mention the applications to quicksort proper and the generalized quicksort of Hennequin, where more phase changes are given. These results provide natural, concrete examples for which the Berry-Esseen bounds are not necessarily proportional to the reciprocal of the standard deviation. Local limit theorems are also derived.