A functional limit theorem for the profile of search trees
From MaRDI portal
Publication:2476407
DOI10.1214/07-AAP457zbMath1143.68019arXivmath/0609385MaRDI QIDQ2476407
Svante Janson, Ralph Neininger, Michael Drmota
Publication date: 19 March 2008
Published in: The Annals of Applied Probability (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0609385
Hilbert spacedifferential equationfunctional limit theorembinary search treeZolotarev metricconcentration methodlevel profile
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Combinatorial probability (60C05) Functional limit theorems; invariance principles (60F17)
Related Items
Limit Theorems for Subtree Size Profiles of Increasing Trees, Pólya Urns Via the Contraction Method, Higher moments of Banach space valued random variables, A limit process for partial match queries in random quadtrees and 2-d trees, Continuous-time digital search tree and a border aggregation model, Edgeworth expansions for profiles of lattice branching random walks, Long and short paths in uniform random recursive dags, Shape Measures of Random Increasing k-trees, General Edgeworth expansions with applications to profiles of random trees, The degree profile of random Pólya trees, Weak convergence of the number of vertices at intermediate levels of random recursive trees, Subtree Sizes in Recursive Trees and Binary Search Trees: Berry–Esseen Bounds and Poisson Approximations, Process convergence for the complexity of radix selection on Markov sources, Heavy tailed solutions of multivariate smoothing transforms, Refined asymptotics for the composition of cyclic urns, A functional limit theorem for the profile of random recursive trees, Search trees: metric aspects and strong limit theorems, Dependence and phase changes in random m‐ary search trees, On martingale tail sums for the path length in random trees, On the Subtree Size Profile of Binary Search trees, A functional limit theorem for the profile of \(b\)-ary trees, Refined quicksort asymptotics, Partial match queries in random quadtrees, Limit theorems for patterns in phylogenetic trees, On a functional contraction method
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Martingales and profile of binary search trees
- The density of the ISE and local limit laws for embedded trees
- The random multisection problem, travelling waves and the distribution of the height of \(m\)-ary search trees
- Profiles of random trees: Limit theorems for random recursive trees and binary search trees
- Width and mode of the profile for some random trees of logarithmic height
- A general limit theorem for recursive algorithms and combinatorial structures
- Transitional behaviors of the average cost of quicksort with median-of-\((2t+1)\)
- The profile of binary search trees
- Estimates of the Distance between Sums of Independent Random Elements in Banach Spaces
- Profiles of random trees: Plane-oriented recursive trees
- Singularity Analysis of Generating Functions
- Approximation of Distributions of Sums of Independent Random Variables with Values in Infinite-Dimensional Spaces
- Ideal Metrics in the Problem of Approximating Distributions of Sums of Independent Random Variables
- Orthogonal decompositions and functional limit theorems for random graph statistics
- An asymptotic theory for Cauchy–Euler differential equations with applications to the analysis of algorithms
- Bimodality and Phase Transitions in the Profile Variance of Random Binary Search Trees
- More Combinatorial Properties of Certain Trees
- Weak convergence of probability measures and random functions in the function space D[0,∞)
- Profiles of random trees: correlation and width of random recursive trees and binary search trees