تقرير
Patricia's Bad Distributions
| العنوان: | Patricia's Bad Distributions |
|---|---|
| المؤلفون: | Addario-Berry, Louigi, Morin, Pat, Neininger, Ralph |
| سنة النشر: | 2024 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Probability, 68P05, 60C05, 68R15, 68P10 |
| الوصف: | The height of a random PATRICIA tree built from independent, identically distributed infinite binary strings with arbitrary diffuse probability distribution $\mu$ on $\{0,1\}^\mathbb{N}$ is studied. We show that the expected height grows asymptotically sublinearly in the number of leaves for any such $\mu$, but can be made to exceed any specific sublinear growth rate by choosing $\mu$ appropriately. Comment: Revised version. Accepted for publication in the proceedings of the 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA2024) |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.4230/LIPIcs.AofA.2024.9 |
| URL الوصول: | http://arxiv.org/abs/2403.05269 |
| رقم الأكسشن: | edsarx.2403.05269 |
| قاعدة البيانات: | arXiv |
| DOI: | 10.4230/LIPIcs.AofA.2024.9 |
|---|