Geodesic
Support and density of the limit $m$-ary search trees distribution
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) (2012).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2012_special_262_a15,
     author = {Chauvin, Brigitte and Liu, Quansheng and Pouyanne, Nicolas},
     title = {Support and density of the limit $m$-ary search trees distribution},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)},
     year = {2012},
     doi = {10.46298/dmtcs.2994},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2994/}
}
TY  - JOUR
AU  - Chauvin, Brigitte
AU  - Liu, Quansheng
AU  - Pouyanne, Nicolas
TI  - Support and density of the limit $m$-ary search trees distribution
JO  - Discrete mathematics & theoretical computer science
PY  - 2012
VL  - DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2994/
DO  - 10.46298/dmtcs.2994
LA  - en
ID  - DMTCS_2012_special_262_a15
ER  - 
%0 Journal Article
%A Chauvin, Brigitte
%A Liu, Quansheng
%A Pouyanne, Nicolas
%T Support and density of the limit $m$-ary search trees distribution
%J Discrete mathematics & theoretical computer science
%D 2012
%V DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2994/
%R 10.46298/dmtcs.2994
%G en
%F DMTCS_2012_special_262_a15
Chauvin, Brigitte; Liu, Quansheng; Pouyanne, Nicolas. Support and density of the limit $m$-ary search trees distribution. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) (2012). doi : 10.46298/dmtcs.2994. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2994/

Cité par Sources :