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

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

$\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