Novel Characteristics of Split Trees by use of Renewal Theory

2010/05/25 by Cecilia Holmgren, Holmgren, Cecilia
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Mathematical Dynamics and Fractals #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1005.4594

openalex publication_date 2010/05/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We investigate characteristics of random split trees introduced by Devroye; split trees include for example binary search trees, m-ary search trees, quadtrees, median of (2k+1)-trees, simplex trees, tries and digital search trees. More precisely: We introduce the use of renewal theory in the studies of split trees, and use this theory to prove several results about split trees. A split tree of cardinality n is constructed by distributing n "balls" (which often represent "key numbers") in a subset of vertices of an infinite tree. One of our main results is to give a relation between the deterministic number of balls n and the random number of vertices N. Devroye has found a central limit law for the depth of the last inserted ball so that most vertices are close to \fracln nμ+O(√(ln n)), where μ is some constant depending on the type of split tree; we sharpen this result by finding an upper bound for the expected number of vertices with depths ≥\fracln nμ+ln^0.5+ε n or depths ≤\fracln nμ+ln^0.5+ε n for any choice of ε>0. We also find the first asymptotic of the variances of the depths of the balls in the tree.

Related

• A Weakly 1-Stable Limiting Distribution for the Number of Random Records and Cuttings in Split Trees
• Congruence properties of depths in some random trees
• The fluctuations of the giant cluster for percolation on random split trees
• Random recursive trees and preferential attachment trees are random split trees
• On a random search tree: asymptotic enumeration of vertices by distance from leaves