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

Chauvin, Brigitte  ; Liu, Quansheng  ; Pouyanne, Nicolas 

Annales de l'I.H.P. Probabilités et statistiques, Tome 50 (2014) no. 2, pp. 628-654

Abstract (VO)

Let $m\ge 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 $m\le 26$, the asymptotic behavior of the process is Gaussian, but for $m\ge 27$ it is no longer Gaussian and a limit $W^{DT}$ of a complex-valued martingale arises. 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\ge 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\stackrel{ℒ}{=}{\mathrm{e}}^{-\lambda T}(Z^{\left(1\right)}+\cdots +Z^{\left(m\right)})$, where $\lambda$ is a particular complex number, $Z^{\left(k\right)}$ are independent complex-valued random variables having the same law as $Z$, $T$ is a ${ℝ}_{+}$-valued random variable independent of the $Z^{\left(k\right)}$, and $\stackrel{ℒ}{=}$ 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.

Résumé

Soit $m\ge 3$ un entier. Très populaire en informatique fondamentale, l’arbre $m$-aire de recherche est une chaîne de Markov à temps discret qui modélise de célèbres algorithmes de tri et de recherche de données. Ce processus aléatoire vérifie une transition de phase bien connue : lorsque $m\le 26$, le comportement asymptotique du processus est gaussien. En revanche, lorsque $m\ge 27$, il n’est plus gaussien et fait apparaître la limite $W^{DT}$ d’une martingale à valeurs complexes. Dans cet article, on considère le processus de branchement multitype qui est le plongement en temps continu de l’arbre $m$-aire de recherche. Ce processus fait l’objet d’une transition de phase du même type. En particulier, lorsque $m\ge 27$, son asymptotique s’exprime à l’aide de la limite $W$ d’une martingale complexe. Grâce à la propriété de branchement, la loi de $W$ est solution d’une équation en distribution du type $Z\stackrel{ℒ}{=}{\mathrm{e}}^{-\lambda T}(Z^{\left(1\right)}+\cdots +Z^{\left(m\right)})$ où $\lambda$ est un nombre complexe particulier, les $Z^{\left(k\right)}$ sont des variables aléatoires complexes indépendantes dont la loi est celle de $Z$, $T$ est une variable aléatoire réelle positive indépendante des $Z^{\left(k\right)}$, et $\stackrel{ℒ}{=}$ désigne l’égalité en distribution. On étudie cette équation en loi par des approches variées. L’existence et l’unicité de solutions sont prouvées par des méthodes de contraction. L’absolue continuité de $W$ et le fait que son support soit le plan complexe tout entier sont démontrés par analyse de Fourier. Enfin, on obtient l’existence de moments exponentiels en considérant $W$ comme la limite d’une cascade de Mandelbrot à valeurs complexes.

Détail

DOI : 10.1214/12-AIHP518

Classification : 60C05, 60J80, 05D40
Keywords: martingale, characteristic function, embedding in continuous time, multitype branching process, smoothing transformation, absolute continuity, support, exponential moments