On The variance of the extremal path length in a symmetric digital trie (Q1262137)

A trie is a digital search tree whose edges are labelled by elements from an alphabet, the leaves contain keys such that the access path from the root to a key is a prefix of that key. The variance of the external path length (sum of all access paths) for binary tries is studied. First, the authors derive the exact formula on the variance for an asymmetric trie, that is, when the probabilities of appearance of 0 and 1 in a key are not the same. Next, they prove that the variance for the binary symmetric tries is asymptotically equal to \(4.35n+n\cdot f(\log_ 2n)\) where f(x) is a periodic function with a very small amplitude and mean zero.