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

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

2012-01-19

arxiv.org/abs/1201.4098v1

Mathematics

Probability

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Support and density of the limit $m$-ary search trees distribution does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Support and density of the limit $m$-ary search trees distribution, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Support and density of the limit $m$-ary search trees distribution will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-254490