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

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

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.

Review text

This paper considers the Markov process that corresponds to random \(m\)-ary search trees. This is a multitype branching process with \(m-1\) types. Each particle of type \(j\) dies with an exponential rate \(j\) and gives rise to a particle of type \(j+1\), except when \(j=m-1\), where the dying particle produces \(m\) particles of type 1. This induces a continuous process on \(\mathbb{R}^{m-1}\) which is denoted by \(X(t)\): here, the \(k\)th coordinate of this vector is the number of particles of type \(k\). It has been known that for \(m \leq 26\), this vector converges (for \(t\rightarrow \infty\)) to a Gaussian. The authors of this paper consider the case where \(m \geq 27\) and give the limiting distribution, which in this case is a linear combination of functions of two Gamma-distributed random variables. They also consider the limiting random variable for the special case where the initial state is a single particle of type 1. Here, they give the asymptotic decay of its characteristic function as well as its Laplace transform close to the origin of the complex plane. To this end, the authors show that this random variable is the solution to a distributional fixed-point equation. They derive theorems for this solution, regarding the asymptotics of its Fourier transform and its relative density with respect to the Lebesgue measure on \(\mathbb{C}\).

Recommendations

Cites work

Cited in

(10)

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)