Paths in a random digital tree: limiting distributions

We study a rule of growing a sequence { t n } of finite subtrees of an infinite m -ary tree T. Independent copies { ω ( n )} of a Bernoulli-type process ω on m letters are used to trace out a sequence of paths in T. The tree t n is obtained by cutting each , at the first node such that at most σ paths out of , pass through it. Denote by H n the length of the longest path, h n the length of the shortest path, and L n the length of the randomly chosen path in t n . It is shown that, in probability, H n – log a n = O (1), h n – log b ( n/ log n ) = 0(1), (or h n – log b ( n/ log log n ) = O (1)), and that is asymptotically normal. The parameters a, b, c depend on the distribution of ω and, in case of a , also on σ . These estimates describe respectively the worst, the best and the typical case behavior of a ‘trie’ search algorithm for a dictionary-type information retrieval system, with σ being the capacity of a page.