A weakly 1-stable distribution for the number of random records and cuttings in split trees
From MaRDI portal
Publication:2996574
DOI10.1239/aap/1300198517zbMath1213.05037arXiv1005.4590OpenAlexW1971974071MaRDI QIDQ2996574
Publication date: 3 May 2011
Published in: Advances in Applied Probability (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1005.4590
Analysis of algorithms (68W40) Central limit and other weak theorems (60F05) Trees (05C05) Searching and sorting (68P10) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05) Data structures (68P05)
Related Items
\(k\)-cut on paths and some trees ⋮ A modification of the random cutting model ⋮ Cutting Edges at Random in Large Recursive Trees ⋮ The \(k\)-cut model in deterministic and random trees ⋮ The total path length of split trees ⋮ The fluctuations of the giant cluster for percolation on random split trees ⋮ Dependence and phase changes in random m‐ary search trees ⋮ Cutting resilient networks -- complete binary trees ⋮ Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey ⋮ The cut-tree of large recursive trees ⋮ Sizes of the largest clusters for supercritical percolation on random recursive trees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The total path length of split trees
- Limiting distributions for additive functionals on Catalan trees
- On the average internal path length of m-ary search trees
- On the analysis of stochastic divide and conquer algorithms
- A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree
- Fixed points with finite variance of a smoothing transformation.
- Size and path length of Patricia tries: Dynamical sources context
- Random Records and Cuttings in Binary Search Trees
- Random cutting and records in deterministic and random trees
- Cutting down very simple trees
- Exponential rate of almost-sure convergence of intrinsic martingales in supercritical branching random walks
- A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree
- Analysis of the space of search trees under the random insertion algorithm
- Universal Limit Laws for Depths in Random Trees
- On the internal path length ofd-dimensional quad trees
- Symmetric fixed points of a smoothing transformation
- Probability: A Graduate Course
- Quicksort asymptotics
- Cutting down random trees
- Analytic Properties of a Generating Function for the Number of Renewals
