pith. sign in

arxiv: 1201.4098 · v1 · pith:XRK27UQLnew · submitted 2012-01-19 · 🧮 math.PR

Support and density of the limit m-ary search trees distribution

classification 🧮 math.PR
keywords complexindependentdensitydistributiongaussianlambdalimitplane
0
0 comments X
read the original abstract

The space requirements of an $m$-ary search tree satisfies a well-known phase transition: when $m\leq 26$, the second order asymptotics is Gaussian. When $m\geq 27$, it is not Gaussian any longer and a limit $W$ of a complex-valued martingale arises. We show that the distribution of $W$ has a square integrable density on the complex plane, that its support is the whole complex plane, and that it has finite exponential moments. The proofs are based on the study of the distributional equation $ W\egalLoi\sum_{k=1}^mV_k^{\lambda}W_k$, where $V_1, ..., V_m$ are the spacings of $(m-1)$ independent random variables uniformly distributed on $[0,1]$, $W_1, ..., W_m$ are independent copies of W which are also independent of $(V_1, ..., V_m)$ and $\lambda$ is a complex number.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.