A weakly 1-stable distribution for the number of random records and cuttings in split trees
From MaRDI portal
Publication:2996574
Abstract: We study the number of random records in an arbitrary split tree (or equivalently, the number of random cuttings required to eliminate the tree). We show that a classical limit theorem for convergence of sums of triangular arrays to infinitely divisible distributions can be used to determine the distribution of this number. After normalization the distributions are shown to be asymptotically weakly 1-stable. This work is a generalization of our earlier results for the random binary search tree, which is one specific case of split trees. Other important examples of split trees include -ary search trees, quadtrees, medians of -trees, simplex trees, tries and digital search trees.
Recommendations
Cites work
- scientific article; zbMATH DE number 1713116 (Why is no real title available?)
- scientific article; zbMATH DE number 4013703 (Why is no real title available?)
- scientific article; zbMATH DE number 2127735 (Why is no real title available?)
- scientific article; zbMATH DE number 192907 (Why is no real title available?)
- scientific article; zbMATH DE number 2046075 (Why is no real title available?)
- scientific article; zbMATH DE number 3349081 (Why is no real title available?)
- A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree
- A probabilistic proof of a weak limit law 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
- Analytic Properties of a Generating Function for the Number of Renewals
- Cutting down random trees
- Cutting down very simple trees
- Digital trees and memoryless sources: from arithmetics to analysis
- Exponential rate of almost-sure convergence of intrinsic martingales in supercritical branching random walks
- Fixed points with finite variance of a smoothing transformation.
- Limiting distributions for additive functionals on Catalan trees
- On the analysis of stochastic divide and conquer algorithms
- On the average internal path length of m-ary search trees
- On the internal path length ofd-dimensional quad trees
- Probability: A Graduate Course
- Quicksort asymptotics
- Random cutting and records in deterministic and random trees
- Random records and cuttings in binary search trees
- Size and path length of Patricia tries: Dynamical sources context
- Symmetric fixed points of a smoothing transformation
- The total path length of split trees
- Universal Limit Laws for Depths in Random Trees
Cited in
(16)- The fluctuations of the giant cluster for percolation on random split trees
- \(k\)-cut on paths and some trees
- Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey
- scientific article; zbMATH DE number 6683495 (Why is no real title available?)
- Random records and cuttings in binary search trees
- Coupling Bertoin's and Aldous-Pitman's representations of the additive coalescent
- The total path length of split trees
- Sizes of the largest clusters for supercritical percolation on random recursive trees
- scientific article; zbMATH DE number 2127735 (Why is no real title available?)
- scientific article; zbMATH DE number 7703259 (Why is no real title available?)
- Cutting edges at random in large recursive trees
- The \(k\)-cut model in deterministic and random trees
- A modification of the random cutting model
- Dependence and phase changes in random \(m\)-ary search trees
- The cut-tree of large recursive trees
- Cutting resilient networks -- complete binary trees
This page was built for publication: A weakly 1-stable distribution for the number of random records and cuttings in split trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2996574)
