Analysis of digital tries with Markovian dependency

A complete characterization of a digital tree, also called a trie, is presented from the depth viewpoint in a Markovian framework, that is, under the assumption that symbols in a key are Markov-dependent. The main findings show that asymptotically, as the number of keys n tends to infinity, the average depth becomes ED_n~(1/ h₁) log N+c\´, and the variance is var D_n~α log n+c", where h₁ is the entropy of the (Markovian-dependent) alphabet, α is a parameter of the probabilistic model and c \´ and c" are constants. The symmetric independent model has α=0, hence in this case var D_n=O(1). Limiting distribution is also derived for the depth D_n, and in particular, it is shown that D_n tends to the normal distribution in all cases except the symmetric independent model. These results extend all previous analyses since most of them have been limited to independent models