Central limit theorems for additive functionals in patricia tries
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914413804519424 |
|---|---|
| author | Ischebeck, Jasper |
| author_facet | Ischebeck, Jasper |
| contents | We give theorems about asymptotic normality of general additive functionals on patricia tries in an i.i.d. setting, derived from results on tries by Janson (2022). These theorems are applied to show asymptotic normality of the distribution of random fringe trees in patricia tries. Formulas for asymptotic mean and variance are given. The proportion of fringe trees with $k$ keys is asymptotically, ignoring oscillations, given by $(1-ρ(k))/(H+J)k(k-1)$ with the source entropy $H$, an entropy-like constant $J$, that is $H$ in the binary case, and an exponentially decreasing function $ρ(k)$. Another application gives asymptotic normality of the independence number. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_14900 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Central limit theorems for additive functionals in patricia tries Ischebeck, Jasper Probability 60F05 (Primary) 68P10, 68P05 (Secondary) We give theorems about asymptotic normality of general additive functionals on patricia tries in an i.i.d. setting, derived from results on tries by Janson (2022). These theorems are applied to show asymptotic normality of the distribution of random fringe trees in patricia tries. Formulas for asymptotic mean and variance are given. The proportion of fringe trees with $k$ keys is asymptotically, ignoring oscillations, given by $(1-ρ(k))/(H+J)k(k-1)$ with the source entropy $H$, an entropy-like constant $J$, that is $H$ in the binary case, and an exponentially decreasing function $ρ(k)$. Another application gives asymptotic normality of the independence number. |
| title | Central limit theorems for additive functionals in patricia tries |
| topic | Probability 60F05 (Primary) 68P10, 68P05 (Secondary) |
| url | https://arxiv.org/abs/2305.14900 |