Limit distributions for multitype branching processes of m-ary search trees

DOI10.1214/12-AIHP518zbMATH Open1318.60013arXiv1112.0256OpenAlexW1968457938MaRDI QIDQ2451114FDOQ2451114

Authors: Brigitte Chauvin, Nicolas Pouyanne, Quansheng Liu 

Publication date: 26 May 2014

Published in: Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

Abstract: A particular continuous-time multitype branching process is considered, it is the continuous-time embedding of a discrete-time process which is very popular in theoretical computer science: the m-ary search tree (m is an integer). There is a well-known phase transition: when m leq 26, the asymptotic behavior of the process is Gaussian, but for m geq 27 it is no more Gaussian and a limit W of a complex-valued martingale arises. Thanks to the branching property it appears as a solution of a smoothing equation of the type Z = e^{-{lambda}T}(Z(1) + ... + Z(m)), where {lambda} in C, the Z(k) are independent copies of Z and T is a R_+-valued random variable, independent of the Z(k). This distributional equation is extensively studied by various approaches. The existence and unicity of solution of the equation are proved by contraction methods. The fact that the distribution of W is absolutely continuous and that its support is the whole complex plane is shown via Fourier analysis. Finally, the existence of exponential moments of W is obtained by considering W as the limit of a complex Mandelbrot cascade.

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

Recommendations

• Support and density of the limit \(m\)-ary search trees distribution
• m‐ary Search trees when m ≥ 27: A strong asymptotics for the space requirements
• Transfer theorems and asymptotic distributional results for m‐ary search trees
• On the height of random m‐ary search trees
• The random multisection problem, travelling waves and the distribution of the height of \(m\)-ary search trees

zbMATH Keywords

branching processeslimiting distribution\(m\)-ary treesPólya urn

Mathematics Subject Classification ID

Combinatorial probability (60C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• Real Analysis and Probability
• The contraction method for recursive algorithms
• Random Fragmentation and Coagulation Processes
• Operator-Stable Probability Distributions on Vector Groups
• Limit distributions for large Pólya urns
• Functional limit theorems for multitype branching processes and generalized Pólya urns.
• Title not available (Why is that?)
• Fixed points of the smoothing transformation
• Limiting distributions for additive functionals on Catalan trees
• An algebraic approach to Pólya processes
• Asymptotic properties and absolute continuity of laws stable by random weighted mean.
• A fixed point theorem for distributions
• Sur une extension de la notion de loi semi-stable. (On an extension of the notion of semi-stable law)
• Moments of distributions attracted to operator-stable laws
• m‐ary Search trees when m ≥ 27: A strong asymptotics for the space requirements
• Classification of large Pólya-Eggenberger urns with regard to their asymptotics
• Convergence of complex multiplicative cascades
• Limit theorems for Mandelbrot's multiplicative cascades.
• Asymptotic properties of supercritical age-dependent branching processes and homogeneous branching random walks
• Phase changes in random \(m\)-ary search trees and generalized quicksort

Cited In (9)

• Support and density of the limit \(m\)-ary search trees distribution
• On the Kesten-Goldie constant
• Absolute continuity of complex martingales and of solutions to complex smoothing equations
• Solutions to complex smoothing equations
• The random multisection problem, travelling waves and the distribution of the height of \(m\)-ary search trees
• On densities for solutions to stochastic fixed point equations
• Balanced multicolour Pólya urns via smoothing systems analysis
• Moment convergence of balanced Pólya processes
• Smoothing equations for large Pólya urns

This page was built for publication: Limit distributions for multitype branching processes of \(m\)-ary search trees

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