تقرير
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 |
---|