Limit Laws for Heights in Generalized Tries and PATRICIA Tries

摘要: Wojciech Szpankowskit Department of Computer Science Purdue University W. LafayeUe, IN 47907 UB.A. spa@cs.purdue.edu We consider digital trees such as (generalized) tries and PATRICIA tries, built from n random strings generated by an unbiased memoryless source (i.e., all symbols are equally likely). study limit laws the height which is defined longest path in trees. It turns out that this also represents number questions required to recognize distinct objects. shall identiry three natural regions distribution~. For region where most probability mas~ concentrated, asymptotic distribution extreme value type (Le., double exponential distribution). Surprisinglyenough, PATIUCIA trie behaves quite differently region; exhibits a Gaussian (with oscillating tcnn) around probable k l = llog2 + /21og2 ~ ~J+l. In fact, concentrates on one or two points. ma."iS concentrated at kI , however, there exist subsequences mass points hI 1 hI, hi 1. derive these results combination analytic methods generating functions, Mellin transform, saddle point method ideas applied mathematics linearization, matching WKB method. present some numerical verification our results.