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 transformrecurrencePoissonization

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• 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)

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

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)