A NOTE ON THE ASYMPTOTIC-BEHAVIOR OF THE DEPTH OF TRIES

We analyze the depth distribution of digital trees called tries. Assum ing that the trie is constructed from n statistically independent bina ry strings, we compute the probability that the depth is equal to k. W e study this probability asymptotically, for n and/or k large. We obta in detailed results for n --> infinity and various ranges of k. This s upplements previous work, which mostly involves computing the limiting distribution as n --> infinity. Our analysis also gives an accurate d escription of the tails of the probability distribution. If the symbol s in the string are zeros and ones, we assume they occur independently with respective probabilities q and p = 1 - q. We study the symmetric model (p = q = 1/2), the nonsymmetric model (p not equal q), and the ''nearly symmetric'' model. In the latter we have n --> infinity and s imultaneously p - q --> 0. Here we obtain a new limiting probability d istribution, that interpolates the well-known extreme value (p = q) an d normal (p not equal q) distributions.