A weakly 1-stable distribution for the number of random records and cuttings in split trees

DOI10.1239/AAP/1300198517zbMATH Open1213.05037arXiv1005.4590OpenAlexW1971974071MaRDI QIDQ2996574FDOQ2996574

Authors: Cecilia Holmgren 

Publication date: 3 May 2011

Published in: Advances in Applied Probability (Search for Journal in Brave)

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 $m$-ary search trees, quadtrees, medians of $(2k+1)$-trees, simplex trees, tries and digital search trees.

Full work available at URL: https://arxiv.org/abs/1005.4590

Recommendations

• scientific article; zbMATH DE number 6683495
• Random records and cuttings in binary search trees
• scientific article; zbMATH DE number 7703259
• Novel characteristics of split trees by use of renewal theory
• Random cutting and records in deterministic and random trees

zbMATH Keywords

stable distributioncutrandom treeinfinitely divisible distributionrecordSplit tree

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Central limit and other weak theorems (60F05) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Data structures (68P05) Searching and sorting (68P10) Combinatorial probability (60C05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the analysis of stochastic divide and conquer algorithms
• Title not available (Why is that?)
• Probability: A Graduate Course
• Title not available (Why is that?)
• A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree
• Limiting distributions for additive functionals on Catalan trees
• Title not available (Why is that?)
• Random cutting and records in deterministic and random trees
• Cutting down very simple trees
• Title not available (Why is that?)
• Cutting down random trees
• Exponential rate of almost-sure convergence of intrinsic martingales in supercritical branching random walks
• Quicksort asymptotics
• Size and path length of Patricia tries: Dynamical sources context
• Digital trees and memoryless sources: from arithmetics to analysis
• 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.
• Analysis of the space of search trees under the random insertion algorithm
• Random records and cuttings in binary search trees
• Universal Limit Laws for Depths in Random Trees
• On the internal path length ofd-dimensional quad trees
• The total path length of split trees
• On the average internal path length of m-ary search trees
• Symmetric fixed points of a smoothing transformation
• Analytic Properties of a Generating Function for the Number of Renewals

Cited In (16)

• Sizes of the largest clusters for supercritical percolation on random recursive trees
• The total path length of split trees
• Cutting edges at random in large recursive trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• Random records and cuttings in binary search trees
• Title not available (Why is that?)
• The \(k\)-cut model in deterministic and random trees
• The fluctuations of the giant cluster for percolation on random split trees
• Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey
• Coupling Bertoin's and Aldous-Pitman's representations of the additive coalescent
• Dependence and phase changes in random \(m\)-ary search trees
• Cutting resilient networks -- complete binary trees
• \(k\)-cut on paths and some trees
• The cut-tree of large recursive trees
• A modification of the random cutting model

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)