We investigate Δ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→∞. It is demonstrated that the centered random variable Δn*=Δn−⌊2log2n⌋ does not have a limit distribution, but rather oscillates between two distributions.
Publié le : 2005-05-14
Classification:
Random trees,
recurrence,
Mellin transform,
poissonization,
05C05,
60C05,
60F05,
68P05,
68P10,
68P20
@article{1115137985,
author = {Christophi, Costas A. and Mahmoud, Hosam M.},
title = {The oscillatory distribution of distances in random tries},
journal = {Ann. Appl. Probab.},
volume = {15},
number = {1A},
year = {2005},
pages = { 1536-1564},
language = {en},
url = {http://dml.mathdoc.fr/item/1115137985}
}
Christophi, Costas A.; Mahmoud, Hosam M. The oscillatory distribution of distances in random tries. Ann. Appl. Probab., Tome 15 (2005) no. 1A, pp. 1536-1564. http://gdmltest.u-ga.fr/item/1115137985/