DMTCS Proceedings, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)

Font Size:  Small  Medium  Large

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

Brigitte Chauvin, Quansheng Liu, Nicolas Pouyanne


The space requirements of an m-ary search tree satisfy a well-known phase transition: when m≤26, the second order asymptotics is Gaussian. When m≥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= &limits;&mathcal;L∑k=1mVkλWk, where V1, ..., Vm are the spacings of (m-1) independent random variables uniformly distributed on [0,1], W1, ..., Wm are independent copies of W which are also independent of (V1, ..., Vm) and λ is a complex number.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional