The oscillatory distribution of distances in random tries

DOI10.1214/105051605000000106MaRDI QIDQ558689zbMATH OpenOpenAlexFDO

Authors Costas A. Christophi, Hosam M. Mahmoud

Publication date 13 July 2005

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0505259

zbMATH Keywords

Mellin transformPoissonizationrecurrence

Mathematics Subject Classification ID

Trees (05C05) Combinatorial probability (60C05) Central limit and other weak theorems (60F05) Data structures (68P05) Searching and sorting (68P10) Information storage and retrieval of data (68P20)

Abstract: 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 oinfty. It is demonstrated that the centered random variable Delta_n^*=Delta_n-lfloor2log_2n floor does not have a limit distribution, but rather oscillates between two distributions.

Recommendations

• Limit distribution of distances in biased random tries
• Distribution of inter-node distances in digital trees
• On The variance of the extremal path length in a symmetric digital trie
• Concentration of Size and Path Length of Tries
• Profiles of Tries

Cites work

• Analytical depoissonization and its applications
• Average case analysis of algorithms on sequences. With a foreword by Philippe Flajolet
• Distribution of distances in random binary search trees.
• File structures using hashing functions
• scientific article; zbMATH DE number 3961005 (Why is no real title available?)
• scientific article; zbMATH DE number 3978406 (Why is no real title available?)
• scientific article; zbMATH DE number 4074878 (Why is no real title available?)
• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 1033192 (Why is no real title available?)
• scientific article; zbMATH DE number 1540682 (Why is no real title available?)
• scientific article; zbMATH DE number 3440485 (Why is no real title available?)
• scientific article; zbMATH DE number 1870234 (Why is no real title available?)
• On the distribution for the duration of a randomized leader election algorithm
• Paths in a random digital tree: limiting distributions
• Periodic oscillations in the analysis of algorithms and their cancellations
• Spanning tree size in random binary search trees.

Cited in

(9)

• Limit laws for the Randić index of random binary tree models
• Labels distance in bucket recursive trees with variable capacities of buckets
• Analysis of Steiner subtrees of random trees for traceroute algorithms
• Limit distribution of distances in biased random tries
• Average-Case Analysis of Cousins in m-ary Tries
• The Wiener index of random digital trees
• ON CLIMBING TRIES
• Distances in random digital search trees
• On the distribution of distances between specified nodes in increasing trees

This page was built for publication: The oscillatory distribution of distances in random tries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q558689)