Second phase changes in random $\boldsymbol{m}$-ary search trees and generalized quicksort: Convergence rates

Hwang, Hsien-Kuei

Ann. Probab., Tome 31 (2003) no. 1, p. 609-629 / Harvested from Project Euclid

Résumé

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\le m\le 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\le m\le 19$ and is $O(n^{-3(3/2-\alpha)})$, where $4/3<\alpha<3/2$ is a parameter depending on $m$ for $20\le m\le 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.

Détail

Publié le : 2003-04-14
Classification:  Convergeance rates,  asymptotic normality,  phase change,  search trees,  quicksort,  method of moments,  local limit theorems