A functional limit theorem for the profile of \(b\)-ary trees
From MaRDI portal
Publication:988760
DOI10.1214/09-AAP640zbMath1208.60030arXiv1010.3092MaRDI QIDQ988760
Publication date: 18 August 2010
Published in: The Annals of Applied Probability (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1010.3092
martingalesanalysis of algorithmsfunctional limit theoremrandom trees\(b\)-ary treesprofile of trees
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Random graphs (graph-theoretic aspects) (05C80) Functional limit theorems; invariance principles (60F17)
Related Items (4)
The degree profile of random Pólya trees ⋮ Random walks with preferential relocations and fading memory: a study through random recursive trees ⋮ On martingale tail sums for the path length in random trees ⋮ Geometry of weighted recursive and affine preferential attachment trees
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
- Unnamed Item
- Unnamed Item
- Martingales and profile of binary search trees
- Profiles of random trees: Limit theorems for random recursive trees and binary search trees
- Large deviations for the weighted height of an extended class of trees
- Weighted height of random trees
- Width and mode of the profile for some random trees of logarithmic height
- A diffusion limit for a class of randomly-growing binary trees
- Branching processes in the analysis of the heights of trees
- Spatial growth of a branching process of particles living in \(R^ n\).
- Uniform convergence of martingales in the branching random walk
- Distances in random plane-oriented recursive trees
- The first birth problem for an age-dependent branching process
- The asymptotic behavior of fragmentation processes
- The SDE solved by local times of a Brownian excursion or bridge derived from the height profile of a random tree or forest
- The profile of binary search trees
- Asymptotic expansions for the Stirling numbers of the first kind
- The continuum random tree. III
- A functional limit theorem for the profile of search trees
- Martingales and large deviations for binary search trees
- Limit laws for local counters in random binary search trees
- Singularity Analysis of Generating Functions
- Profiles of Tries
- The convergence of a branching Brownian motion used as a model describing the spread of an epidemic
- A note on the height of binary search trees
- Martingale convergence in the branching random walk
- On the Altitude of Nodes in Random Trees
- Note on the heights of random recursive trees and random m‐ary search trees
- On the profile of random trees
- Bimodality and Phase Transitions in the Profile Variance of Random Binary Search Trees
- Profile of Tries
- Optimal variable length codes (arbitrary symbol cost and equal code word probability)
- DISCRETIZATION METHODS FOR HOMOGENEOUS FRAGMENTATIONS
- Profiles of random trees: correlation and width of random recursive trees and binary search trees
This page was built for publication: A functional limit theorem for the profile of \(b\)-ary trees
