
doi: 10.1007/10719839_31
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). We study limit laws of the height which is defined as the longest path in such trees. For tries, in the region where most of the probability mass is concentrated, the asymptotic distribution is of extreme value type (i.e., double exponential distribution). Surprisingly enough, the height of the PATRICIA trie behaves quite differently in this region: It exhibits an exponential of a Gaussian distribution (with an oscillating term) around the most probable value \(k_1=\lfloor \log_2 n + \sqrt{2\log_2 n} -- \frac{3}{2}\rfloor + 1\). In fact, the asymptotic distribution of PATRICIA height concentrates on one or two points. For most n all the mass is concentrated at k1, however, there exist subsequences of n such that the mass is on the two points k1 − 1 and k1, or k1 and k1 + 1. We derive these results by a combination of analytic methods such as generating functions, Mellin transform, the saddle point method and ideas of applied mathematics such as linearization, asymptotic matching and the WKB method.
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 4 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
