On the average depth of asymmetric LC-tries

Andersson and Nilsson have already shown that the average depth Dn of random LC-tries is only Θ(log∗n) when the keys are produced by a symmetric memoryless process, and that Dn=O(loglogn) when the process is asymmetric. In this paper we refine the second estimate by showing that asymptotically (with n→∞): Dn∼1ηloglogn, where n is the number of keys inserted in a trie, η=−log(1−h/h−∞), h=−plogp−qlogq is the entropy of a binary memoryless source with probabilities p, q=1−p (p≠q), and h−∞=−logmin(p,q).