Dependence between Path-length and Size in Random Digital Trees

Michael Fuchs, Hsien-Kuei Hwang

We study the size and the external path length of random tries and show that they are asymptotically independent in the asymmetric case but strongly dependent with small periodic f…