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

作者：Chauvin Brigitte^*; Liu Quansheng; Pouyanne Nicolas

来源：Annales de l Institut Henri Poincare-Probabilites et Statistiques, 2014, 50(2): 628-654.

DOI：10.1214/12-AIHP518

• Martingale
• Characteristic function
• Embedding in continuous time
• Multitype branching process
• Smoothing transformation
• Absolute continuity
• Support
• Exponential moments

Let m %26gt;= 3 be an integer. The so-called m-ary search tree is a discrete time Markov chain which is very popular in theoretical computer science, modelling famous algorithms used in searching and sorting. This random process satisfies a well-known phase transition: when in %26lt;= 26, the asymptotic behavior of the process is Gaussian, but for m %26gt;= 27 it is no longer Gaussian and a limit W-DT of a complex-valued martingale arises. %26lt;br%26gt;In this paper, we consider the multitype branching process which is the continuous time version of the m-ary search tree. This process satisfies a phase transition of the same kind. In particular, when m %26gt;= 27, a limit W of a complex-valued martingale intervenes in its asymptotics. Thanks to the branching property, the law of W satisfies a smoothing equation of the type Z((sic)) e-(lambda t) (Z((1))+ ... + Z((m))), where lambda is a particular complex number, Z((k)) are independent complex-valued random variables having the same law as Z, T is a R(+-)valued random variable independent of the Z((k)), and L-(sic) denotes equality in law. This distributional equation is extensively studied by various approaches. The existence and uniqueness 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.

• 出版日期2014-5