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
\log...
...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.

Bibliography

CH01
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).

Hwa02
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 http://algo.stat.sinica.edu.tw/, 2002.

LM94
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.