Brigitte Chauvin ; Quansheng Liu ; Nicolas Pouyanne
-
Support and density of the limit $m$-ary search trees distribution
dmtcs:2994 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2012,
DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
-
https://doi.org/10.46298/dmtcs.2994
Support and density of the limit $m$-ary search trees distribution
Authors: Brigitte Chauvin 1; Quansheng Liu 2; Nicolas Pouyanne 1
NULL##NULL##NULL
Brigitte Chauvin;Quansheng Liu;Nicolas Pouyanne
1 Laboratoire de Mathématiques de Versailles
2 Laboratoire de Mathématiques de Bretagne Atlantique
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 \overset{\mathcal{L}}{=} \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.
Volume: DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
Asymptotic properties of supercritical age-dependent branching processes and homogeneous branching random walks
2 Documents citing this article
Source : OpenCitations
Chauvin, Brigitte; Mailler, CĂŠcile; Pouyanne, Nicolas, 2013, Smoothing Equations For Large PĂłlya Urns, Journal Of Theoretical Probability, 28, 3, pp. 923-957, 10.1007/s10959-013-0530-z.
Leckey, Kevin, 2018, On Densities For Solutions To Stochastic Fixed Point Equations, Random Structures And Algorithms, 54, 3, pp. 528-558, 10.1002/rsa.20799.