Patricia's Bad Distributions

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.