Paths in a random digital tree: limiting distributions

DOI10.2307/1427240zbMath0588.60012OpenAlexW2018795275MaRDI QIDQ3715948

Boris G. Pittel

Publication date: 1986

Published in: Unnamed Author (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/1427240

zbMATH Keywords

length of the shortest pathsearch algorithm for a dictionary-type information retrieval system

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Combinatorial probability (60C05)

Related Items (31)

Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach ⋮ On the distribution for the duration of a randomized leader election algorithm ⋮ A diffusion limit for a class of randomly-growing binary trees ⋮ A note on the probabilistic analysis of patricia trees ⋮ Phase transition in a generalized Eden growth model on a tree ⋮ Rounding of continuous random variables and oscillatory asymptotics ⋮ Smoothed heights of tries and patricia tries ⋮ The Satisfiability Threshold fork-XORSAT ⋮ Exact and asymptotic distributions in digital and binary search trees ⋮ On the height of digital trees and related problems ⋮ On tries, contention trees and their analysis ⋮ Asymptotics and statistics on Fishburn matrices and their generalizations ⋮ A characterization of digital search trees from the successful search viewpoint ⋮ Improved behaviour of tries by adaptive branching ⋮ The expected profile of digital search trees ⋮ The oscillatory distribution of distances in random tries ⋮ On the silhouette of binary search trees ⋮ Profile of Tries ⋮ Multiple choice tries and distributed hash tables ⋮ How many random questions are necessary to identify \(n\) distinct objects? ⋮ Imbalance in random digital trees ⋮ Renewal theory in the analysis of tries and strings ⋮ Expected worst-case partial match in random quadtries ⋮ Limit distribution of distances in biased random tries ⋮ Universal Limit Laws for Depths in Random Trees ⋮ A Random Graph With a Subcritical Number of Edges ⋮ A binomial splitting process in connection with corner parking problems ⋮ Some results on tries with adaptive branching. ⋮ Trie size in a dynamic list structure ⋮ Asymptotic enumeration of sparse graphs with a minimum degree constraint ⋮ Laws of large numbers and tail inequalities for random tries and PATRICIA trees

This page was built for publication: Paths in a random digital tree: limiting distributions