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

Chauvin, Brigitte; Liu, Quansheng; Pouyanne, Nicolas

doi:10.1214/12-AIHP518

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.

Résumé
Abstract

Soit $m \geq 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 \leq 26$ , le comportement asymptotique du processus est gaussien. En revanche, lorsque $m \geq 27$ , il n’est plus gaussien et fait apparaître la limite $W^{D T}$ 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 \geq 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 \overset{ℒ}{=} e^{- λ T} (Z^{(1)} + \dots + Z^{(m)})$ où $λ$ est un nombre complexe particulier, les $Z^{(k)}$ 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^{(k)}$ , et $\overset{ℒ}{=}$ 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.

Let $m \geq 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 \leq 26$ , the asymptotic behavior of the process is Gaussian, but for $m \geq 27$ it is no longer Gaussian and a limit $W^{D T}$ 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 \geq 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 \overset{ℒ}{=} e^{- λ T} (Z^{(1)} + \dots + Z^{(m)})$ , where $λ$ is a particular complex number, $Z^{(k)}$ are independent complex-valued random variables having the same law as $Z$ , $T$ is a $ℝ_{+}$ -valued random variable independent of the $Z^{(k)}$ , and $\overset{ℒ}{=}$ 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.

DOI : 10.1214/12-AIHP518

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

@article{AIHPB_2014__50_2_628_0,
     author = {Chauvin, Brigitte and Liu, Quansheng and Pouyanne, Nicolas},
     title = {Limit distributions for multitype branching processes of $m$-ary search trees},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     pages = {628--654},
     publisher = {Gauthier-Villars},
     volume = {50},
     number = {2},
     year = {2014},
     doi = {10.1214/12-AIHP518},
     mrnumber = {3189087},
     language = {en},
     url = {https://www.numdam.org/articles/10.1214/12-AIHP518/}
}

TY  - JOUR
AU  - Chauvin, Brigitte
AU  - Liu, Quansheng
AU  - Pouyanne, Nicolas
TI  - Limit distributions for multitype branching processes of $m$-ary search trees
JO  - Annales de l'I.H.P. Probabilités et statistiques
PY  - 2014
SP  - 628
EP  - 654
VL  - 50
IS  - 2
PB  - Gauthier-Villars
UR  - https://www.numdam.org/articles/10.1214/12-AIHP518/
DO  - 10.1214/12-AIHP518
LA  - en
ID  - AIHPB_2014__50_2_628_0
ER  -

%0 Journal Article
%A Chauvin, Brigitte
%A Liu, Quansheng
%A Pouyanne, Nicolas
%T Limit distributions for multitype branching processes of $m$-ary search trees
%J Annales de l'I.H.P. Probabilités et statistiques
%D 2014
%P 628-654
%V 50
%N 2
%I Gauthier-Villars
%U https://www.numdam.org/articles/10.1214/12-AIHP518/
%R 10.1214/12-AIHP518
%G en
%F AIHPB_2014__50_2_628_0

Chauvin, Brigitte; Liu, Quansheng; Pouyanne, Nicolas. Limit distributions for multitype branching processes of $m$-ary search trees. Annales de l'I.H.P. Probabilités et statistiques, Tome 50 (2014) no. 2, pp. 628-654. doi : 10.1214/12-AIHP518. https://www.numdam.org/articles/10.1214/12-AIHP518/

Bibliographie
Cité par

[1] K. B. Athreya and P. Ney. Branching Processes. Springer, New York, 1972. | MR | Zbl

[2] J. Barral, X. Jin and B. Mandelbrot. Convergence of complex multiplicative cascades. Ann. Appl. Probab. 20 (2010) 1219-1252. | MR | Zbl

[3] J. Bertoin. Random Fragmentation and Coagulation Processes. Cambridge Studies in Advanced Mathematics. Cambridge Univ. Press, Cambridge, 2006. | MR | Zbl

[4] B. Chauvin and N. Pouyanne. $m$ -ary search trees when $m > 26$ : A strong asymptotics for the space requirements. Random Structures Algorithms 24 (2004) 133-154. | MR | Zbl

[5] B. Chauvin, N. Pouyanne and R. Sahnoun. Limit distributions for large Pólya urns. Ann. Appl. Probab. 21 (2011) 1-32. | MR | Zbl

[6] H.-H. Chern and H.-K. Hwang. Phase changes in random $m$ -ary search trees and generalized quicksort. Random Structures Algorithms 19 (2001) 316-358. | MR | Zbl

[7] R. M. Dudley. Real Analysis and Probability. Cambridge Univ. Press, Cambridge, 2002. | MR | Zbl

[8] R. Durrett and T. Liggett. Fixed points of the smoothing transformation. Z. Wahrsch. verw. Gebiete 64 (1983) 275-301. | MR | Zbl

[9] J. A. Fill and N. Kapur. The space requirement of $m$ -ary search trees: Distributional asymptotics for $m \geq 27$ . In Proceedings of the 7th Iranian Conference, Tehran, 2004. Available at ArXiv:math.PR/0405144. | MR

[10] Y. Guivarc'H. Sur une extension de la notion de loi semi-stable. Ann. Inst. Henri Poincaré Probab. Stat. 26 (1990) 261-285. | Numdam | MR | Zbl

[11] W. N. Hudson, J. A. Veeh and D. C. Weiner. Moments of distributions attracted to operator-stable laws. J. Multivariate Anal. 24 (1988) 1-10. | MR | Zbl

[12] S. Janson. Functional limit theorem for multitype branching processes and generalized Pólya urns. Stochastic Process. Appl. 110 (2004) 177-245. | MR | Zbl

[13] Q. Liu. Asymptotic properties of supercritical age-dependent branching processes and homogeneous branching random walks. Stochastic Process. Appl. 82 (1999) 61-87. | MR | Zbl

[14] Q. Liu. Asymptotic properties and absolute continuity of laws stable by random weighted mean. Stochastic Process. Appl. 95 (2001) 83-107. | MR | Zbl

[15] Q. Liu and A. Rouault. Limit theorems for Mandelbrot's multiplicative cascades. Ann. Appl. Probab. 10 (2000) 218-239. | MR | Zbl

[16] H. M. Mahmoud. Evolution of Random Search Trees. Wiley, New York, 1992. | MR | Zbl

[17] J. R. Norris. Markov Chains. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge Univ. Press, Cambridge, 1997. | MR | Zbl

[18] N. Pouyanne. Classification of large Pólya-Eggenberger urns with regard to their asymptotics. In 2005 International Conference on Analysis of Algorithms. Discrete Math. Theor. Comput. Sci. Proc., AD. Assoc. Discrete Math. Theor. Comput. Sci., Nancy 275-285, 2005 (electronic). | MR | Zbl

[19] N. Pouyanne. An algebraic approach to Pólya processes. Ann. Inst. Henri Poincaré Probab. Stat. 44 (2008) 293-323. | Numdam | MR | Zbl

[20] U. Rösler. A fixed point theorem for distributions. Stochastic Process. Appl. 42 (1992) 195-214. | Zbl

[21] U. Rösler and L. Rüschendorf. The contraction method for recursive algorithms. Algorithmica 29 (2001) 3-33. | MR | Zbl

[22] M. Sharpe. Operator-stable probability distribution on vector groups. Trans. Amer. Math. Soc. 136 (1969) 51-65. | MR | Zbl

Leckey, Kevin On densities for solutions to stochastic fixed point equations, Random Structures Algorithms, Volume 54 (2019) no. 3, p. 528 | DOI:10.1002/rsa.20799
Damek, Ewa; Mentemeier, Sebastian Absolute continuity of complex martingales and of solutions to complex smoothing equations, Electronic Communications in Probability, Volume 23 (2018) no. none | DOI:10.1214/18-ecp155
Janson, Svante; Pouyanne, Nicolas Moment convergence of balanced Pólya processes, Electronic Journal of Probability, Volume 23 (2018) no. none | DOI:10.1214/17-ejp80
Mailler, Cécile Balanced multicolour Pólya urns via smoothing systems analysis, Latin American Journal of Probability and Mathematical Statistics, Volume 15 (2018) no. 1, p. 375 | DOI:10.30757/alea.v15-16
Meiners, Matthias; Mentemeier, Sebastian Solutions to complex smoothing equations, Probability Theory and Related Fields, Volume 168 (2017) no. 1-2, p. 199 | DOI:10.1007/s00440-016-0709-1
Buraczewski, D.; Damek, E.; Zienkiewicz, J. On the Kesten–Goldie constant, Journal of Difference Equations and Applications, Volume 22 (2016) no. 11, p. 1646 | DOI:10.1080/10236198.2016.1234613
Chauvin, Brigitte; Mailler, Cécile; Pouyanne, Nicolas Smoothing Equations for Large Pólya Urns, Journal of Theoretical Probability, Volume 28 (2015) no. 3, p. 923 | DOI:10.1007/s10959-013-0530-z

Cité par 7 documents. Sources : Crossref