The oscillatory distribution of distances in random tries

DOI10.1214/105051605000000106zbMATH Open1071.60007arXivmath/0505259OpenAlexW3099976229MaRDI QIDQ558689FDOQ558689

Hosam M. Mahmoud, Costas A. Christophi

Publication date: 13 July 2005

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the distribution for the duration of a randomized leader election algorithm
• Title not available (Why is that?)
• Periodic oscillations in the analysis of algorithms and their cancellations
• Title not available (Why is that?)
• Distribution of distances in random binary search trees.
• File structures using hashing functions
• Analytical depoissonization and its applications
• Average case analysis of algorithms on sequences. With a foreword by Philippe Flajolet
• Title not available (Why is that?)
• Paths in a random digital tree: limiting distributions
• Title not available (Why is that?)
• Spanning tree size in random binary search trees.
• Title not available (Why is that?)

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
• The Wiener Index of Random Digital Trees
• ON CLIMBING TRIES
• Labels distance in bucket recursive trees with variable capacities of buckets
• 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)