The oscillatory distribution of distances in random tries

Details The oscillatory distribution of distances in random tries The oscillatory distribution of distances in random tries

2005-05-12

arxiv.org/abs/math/0505259v1

Annals of Applied Probability 2005, Vol. 15, No. 2, 1536-1564

Mathematics

Probability

Published at http://dx.doi.org/10.1214/105051605000000106 in the Annals of Applied Probability (http://www.imstat.org/aap/) by

Scientific paper

10.1214/105051605000000106

We investigate \Delta_n, the distance between randomly selected pairs of nodes among n keys in a random trie, which is a kind of digital tree. Analytical techniques, such as the Mellin transform and an excursion between poissonization and depoissonization, capture small fluctuations in the mean and variance of these random distances. The mean increases logarithmically in the number of keys, but curiously enough the variance remains O(1), as n\to\infty. It is demonstrated that the centered random variable \Delta_n^*=\Delta_n-\lfloor2\log_2n\rfloor does not have a limit distribution, but rather oscillates between two distributions.

Affiliated with

Also associated with

No associations

Rating

The oscillatory distribution of distances in random tries does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The oscillatory distribution of distances in random tries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The oscillatory distribution of distances in random tries will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-163296