Novel characteristics of split trees by use of renewal theory

DOI10.1214/EJP.V17-1723MaRDI QIDQ428606zbMATH OpenOpenAlexFDO

Authors Cecilia Holmgren

Publication date 22 June 2012

Published in Electronic Journal of Probability (Search for Journal in Brave)

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

zbMATH Keywords

renewal theoryrandom treessplit trees

Mathematics Subject Classification ID

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

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 $fraclnnmu+mathcalOBig(sqrtlnnBig)$, where $mu$ 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 $geqfraclnnmu+l{n}^{0.5+epsilon}n$ or depths $leqfraclnnmu+l{n}^{0.5+epsilon}n$ for any choice of $epsilon>0$. We also find the first asymptotic of the variances of the depths of the balls in the tree.

Recommendations

• Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey
• A New Characterization of Trees
• Implicit renewal theory and power tails on trees
• scientific article; zbMATH DE number 6683495
• Regenerative tree growth: Markovian embedding of fragmenters, bifurcators, and bead splitting processes
• Renewal processes, population dynamics, and unimodular trees
• Survival Trees by Goodness of Split
• The contour of splitting trees is a Lévy process
• Implicit renewal theorem for trees with general weights

Cited in

(18)

• The asymptotic distribution of cluster sizes for supercritical percolation on random split trees
• Inversions in split trees and conditional Galton-Watson trees
• Embedding small digraphs and permutations in binary trees and split trees
• The fluctuations of the giant cluster for percolation on random split trees
• Random recursive trees and preferential attachment trees are random split trees
• \(k\)-cut on paths and some trees
• Tree limits and limits of random trees
• Renewal theory in the analysis of tries and strings
• Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey
• Renewals for exponentially increasing lifetimes, with an application to digital search trees
• A binomial splitting process in connection with corner parking problems
• Analysis of \(d\)-ary tree algorithms with successive interference cancellation
• Voronoi cells in random split trees
• The total path length of split trees
• A weakly 1-stable distribution for the number of random records and cuttings in split trees
• scientific article; zbMATH DE number 7703259 (Why is no real title available?)
• Permutations in binary trees and split trees
• The \(k\)-cut model in deterministic and random trees

This page was built for publication: Novel characteristics of split trees by use of renewal theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q428606)