printable pdf
比利时vs摩洛哥足彩 ,
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

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