Nicolas Pouyanne: What Happens When $m\geq 27$?

This is a joint work with Brigitte Chauvin.

It is known that the joint distribution of the number of nodes of each type of a $m$-ary search tree is multivariate normal when $m\leq 26$ ([LM94], [CH01], [Hwa02]).

When $m\geq 27$, we show the following strong ($L^2$) asymptotics of the random vector $X_n=(X_n^{(1)},\dots ,X_n^{(m-1)})$, where $X_n^{(i)}$ denotes the number of nodes containing $i-1$ keys after having introduced $n$ keys in the tree: there exists deterministic vectors $X$, $C$ and $S$ and random variables $\rho$ and $\varphi$ such that

\begin{displaymath}\Vert {{X_n-nX}\over {n^\sigma}}- \rho \big( C\cos (\tau
...rphi )\big) \Vert _{{\rm L}^2}
\longrightarrow _{n\to \infty}0;\end{displaymath}

$\sigma$ and $\tau$ denote the real and imaginary parts of one of the eigenvalues of the transition matrix, having the second greatest real part.


Hua-Huai Chern and Hsien-Kuei Hwang.
Phase changes in random $m$-ary search trees and generalized quicksort.
Random Structures Algorithms, 19(3-4):316-358, 2001.
Analysis of algorithms (Krynica Morska, 2000).

Hsien-Kuei Hwang.
Second phase changes in random $m$-ary search trees and generalized quicksort: convergence rates.
To appear in the Annals of Probability. Paper available at, 2002.

William Lew and Hosam M. Mahmoud.
The joint distribution of elastic buckets in multiway search trees.
SIAM J. Comput., 23(5):1050-1074, 1994.

Back to the Index

Please send comments and corrections to Thomas Klausner.