Support and density of the limit $m$-ary search trees distribution
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2012-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2994/pdf |
| _version_ | 1797270363224145920 |
|---|---|
| author | Brigitte Chauvin Quansheng Liu Nicolas Pouyanne |
| author_facet | Brigitte Chauvin Quansheng Liu Nicolas Pouyanne |
| author_sort | Brigitte Chauvin |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:03:05Z |
| format | Article |
| id | doaj.art-92ca2e096b5d42a9ade960cef2cae1d1 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:03:05Z |
| publishDate | 2012-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-92ca2e096b5d42a9ade960cef2cae1d12024-03-07T14:50:50ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502012-01-01DMTCS Proceedings vol. AQ,...Proceedings10.46298/dmtcs.29942994Support and density of the limit $m$-ary search trees distributionBrigitte Chauvin0Quansheng Liu1Nicolas Pouyanne2Laboratoire de Mathématiques de VersaillesLaboratoire de Mathématiques de Bretagne AtlantiqueLaboratoire de Mathématiques de VersaillesThe 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.https://dmtcs.episciences.org/2994/pdf[math.math-pr] mathematics [math]/probability [math.pr] |
| spellingShingle | Brigitte Chauvin Quansheng Liu Nicolas Pouyanne Support and density of the limit $m$-ary search trees distribution Discrete Mathematics & Theoretical Computer Science [math.math-pr] mathematics [math]/probability [math.pr] |
| title | Support and density of the limit $m$-ary search trees distribution |
| title_full | Support and density of the limit $m$-ary search trees distribution |
| title_fullStr | Support and density of the limit $m$-ary search trees distribution |
| title_full_unstemmed | Support and density of the limit $m$-ary search trees distribution |
| title_short | Support and density of the limit $m$-ary search trees distribution |
| title_sort | support and density of the limit m ary search trees distribution |
| topic | [math.math-pr] mathematics [math]/probability [math.pr] |
| url | https://dmtcs.episciences.org/2994/pdf |
| work_keys_str_mv | AT brigittechauvin supportanddensityofthelimitmarysearchtreesdistribution AT quanshengliu supportanddensityofthelimitmarysearchtreesdistribution AT nicolaspouyanne supportanddensityofthelimitmarysearchtreesdistribution |