A Weakly 1-Stable Limiting Distribution for the Number of Random Records and Cuttings in Split Trees

Details A Weakly 1-Stable Limiting Distribution for the Number of Random Records and Cuttings in Split Trees A Weakly 1-Stable Limiting Distribution for the Number of Random Records and Cuttings in Split Trees

2010-05-25

arxiv.org/abs/1005.4590v1

Mathematics

Probability

44 pages, 2 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A Weakly 1-Stable Limiting Distribution for the Number of Random Records and Cuttings in Split Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Weakly 1-Stable Limiting Distribution for the Number of Random Records and Cuttings in Split Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Weakly 1-Stable Limiting Distribution for the Number of Random Records and Cuttings in Split Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-298417