##### Department of Mathematics,

University of California San Diego

****************************

### Math 288 - Probability

## Nevin Kapur

#### Cal Tech

## Additive functionals on multiway search trees

##### Abstract:

We derive asymptotics of moments and limiting distributions, under the random permutation model on $m$-ary search trees on $n$~keys, of functionals that satisfy recurrence relations of a simple additive form. Many important functionals including the space requirement, internal path length, and the so-called shape functional fall under this framework. The limiting behavior of these functionals exhibit intriguing phase changes. For suitably ``small'' input (or {\it toll}) sequences we have asymptotic normality if $m \leq 26$ and typically periodic behavior otherwise. For ``moderate'' toll sequences we have convergence to non-normal distributions if $m \leq m_{0}$ (where $m_{0} \geq 26$) and typically periodic behavior otherwise. For ``large'' toll sequences we have convergence to non-normal distributions for all values of~$m$. Recent research greatly sharpens the understanding of the periodic cases. For example, Chauvin and Pouyanne have shown that for $m \geq 27$ fixed, the space requirement equals $$\mu(n+1) + 2 \Re[n^{\lambda_{2}} \Lambda] + \epsilon_{n} n^{\Re\lambda_{2}},$$ where $\mu \in \bf{R}$ and $\lambda_{2} \in \bf{C}$ are certain constants, $\Lambda$ is a complex-valued random variable, and $\epsilon_{n} \to 0$ a.s.\ and in~$L^{2}$ as $n \to \infty$. Using the elementary but powerful ``contraction method,'' we identify the distribution of~$\Lambda$. As time and research progress permits, we will show how the periodic-case result can be extended rather generally to other additive functionals under the random permutation model, and beyond those, to generalized P\'olya urn schemes and multi-type branching processes. (This is joint work with Jim Fill.)

Host: Jason Schweinsberg

### February 2, 2006

### 9:00 AM

### AP&M 6218

****************************