Search trees: metric aspects and strong limit theorems
From MaRDI portal
Publication:2454410
DOI10.1214/13-AAP948zbMath1294.60009arXiv1209.2546OpenAlexW3099091475MaRDI QIDQ2454410
Publication date: 13 June 2014
Published in: The Annals of Applied Probability (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1209.2546
Wiener indexvector-valued martingalesmetric treessilhouettepath lengthDoob-Martin compactificationsubtree size metric
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Probability theory on algebraic and topological structures (60B99)
Related Items (2)
Cites Work
- Trickle-down processes and their boundaries
- Denumerable Markov chains. Generating functions, boundary theory, random walks on trees.
- Martingales and profile of binary search trees
- Profiles of random trees: Limit theorems for random recursive trees and binary search trees
- On the silhouette of binary search trees
- Random walks on discrete groups: Boundary and entropy
- The profile of binary search trees
- A functional limit theorem for the profile of search trees
- Martingales and large deviations for binary search trees
- Random Trees
- Subtree Sizes in Recursive Trees and Binary Search Trees: Berry–Esseen Bounds and Poisson Approximations
- A limiting distribution for quicksort
- A note on the height of binary search trees
- Chernoff's theorem in the branching random walk
- Foundations of Modern Probability
- On the Subtree Size Profile of Binary Search trees
- Random Walks on Infinite Graphs and Groups
- The Martin boundary for Polya's urn scheme, and an application to stochastic population growth
- A limit theorem for “quicksort”
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Search trees: metric aspects and strong limit theorems
