Limit distribution of distances in biased random tries

DOI10.1239/jap/1152413729zbMath1102.68021OpenAlexW2072064628MaRDI QIDQ3410921

Rafik Aguech, Nabil Lasmar, Hosam M. Mahmoud

Publication date: 16 November 2006

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

Full work available at URL: https://doi.org/10.1239/jap/1152413729

zbMATH Keywords

Mellin transformfixed pointrecurrencecontraction methodrandom treePoissonization

Mathematics Subject Classification ID

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

Related Items

Distances in random digital search trees ⋮ Average-Case Analysis of Cousins in m-ary Tries ⋮ Imbalance in random digital trees ⋮ The Wiener Index of Random Digital Trees

Cites Work

• Unnamed Item
• The oscillatory distribution of distances in random tries
• Mellin transforms and asymptotics: Harmonic sums
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• Analytical depoissonization and its applications
• A general limit theorem for recursive algorithms and combinatorial structures
• The contraction method for recursive algorithms
• On the analysis of stochastic divide and conquer algorithms
• On a multivariate contraction method for random recursive structures with applications to Quicksort
• Paths in a random digital tree: limiting distributions
• An asymptotic theory for Cauchy–Euler differential equations with applications to the analysis of algorithms
• Probability metrics and recursive algorithms
• A limit theorem for “quicksort”