Patricia's Bad Distributions

Abstract

The height of a random PATRICIA tree built from independent, identically distributed infinite binary strings with arbitrary diffuse probability distribution $\hat{I}¼$ on $\{0,1{\}}^{\mathbb{N}}$ is studied. We show that the expected height grows asymptotically sublinearly in the number of leaves for any such $\hat{I}¼$, but can be made to exceed any specific sublinear growth rate by choosing $\hat{I}¼$ appropriately.

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)