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

Brigitte Chauvin; Quansheng Liu; Nicolas Pouyanne

Annales de l'I.H.P. Probabilités et statistiques (2014)

  • Volume: 50, Issue: 2, page 628-654
  • ISSN: 0246-0203

Abstract

top
Let m ≥ 3 be an integer. The so-called m -ary search treeis 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 ≤ 26 , the asymptotic behavior of the process is Gaussian, but for m ≥ 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 ≥ 27 , a limit W of a complex-valued martingale intervenes in its asymptotics. Thanks to the branching property, the law of W satisfies asmoothingequation of the type Z = ℒ e - λ T ( Z ( 1 ) + ⋯ + 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 = ℒ 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.

How to cite

top

Chauvin, Brigitte, Liu, Quansheng, and Pouyanne, Nicolas. "Limit distributions for multitype branching processes of $m$-ary search trees." Annales de l'I.H.P. Probabilités et statistiques 50.2 (2014): 628-654. <http://eudml.org/doc/271974>.

@article{Chauvin2014,
abstract = {Let $m\ge 3$ be an integer. The so-called$m$-ary search treeis 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 asmoothingequation of the type $Z\stackrel\{ \mathcal \{L\}\}\{=\}\mathrm \{e\}^\{-\lambda T\}(Z^\{(1)\}+\cdots +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 $\mathbb \{R\}_\{+\}$-valued random variable independent of the $Z^\{(k)\}$, and $\stackrel\{ \mathcal \{L\}\}\{=\}$ 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.},
author = {Chauvin, Brigitte, Liu, Quansheng, Pouyanne, Nicolas},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {martingale; characteristic function; embedding in continuous time; multitype branching process; smoothing transformation; absolute continuity; support; exponential moments; -ary trees; branching processes; Pólya urn; limiting distribution},
language = {eng},
number = {2},
pages = {628-654},
publisher = {Gauthier-Villars},
title = {Limit distributions for multitype branching processes of $m$-ary search trees},
url = {http://eudml.org/doc/271974},
volume = {50},
year = {2014},
}

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
PB - Gauthier-Villars
VL - 50
IS - 2
SP - 628
EP - 654
AB - Let $m\ge 3$ be an integer. The so-called$m$-ary search treeis 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 asmoothingequation of the type $Z\stackrel{ \mathcal {L}}{=}\mathrm {e}^{-\lambda T}(Z^{(1)}+\cdots +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 $\mathbb {R}_{+}$-valued random variable independent of the $Z^{(k)}$, and $\stackrel{ \mathcal {L}}{=}$ 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.
LA - eng
KW - martingale; characteristic function; embedding in continuous time; multitype branching process; smoothing transformation; absolute continuity; support; exponential moments; -ary trees; branching processes; Pólya urn; limiting distribution
UR - http://eudml.org/doc/271974
ER -

References

top
  1. [1] K. B. Athreya and P. Ney. Branching Processes. Springer, New York, 1972. Zbl0259.60002MR373040
  2. [2] J. Barral, X. Jin and B. Mandelbrot. Convergence of complex multiplicative cascades. Ann. Appl. Probab.20 (2010) 1219–1252. Zbl1221.60028MR2676938
  3. [3] J. Bertoin. Random Fragmentation and Coagulation Processes. Cambridge Studies in Advanced Mathematics. Cambridge Univ. Press, Cambridge, 2006. Zbl1107.60002MR2253162
  4. [4] B. Chauvin and N. Pouyanne. m -ary search trees when m g t ; 26 : A strong asymptotics for the space requirements. Random Structures Algorithms24 (2004) 133–154. Zbl1037.60027MR2035872
  5. [5] B. Chauvin, N. Pouyanne and R. Sahnoun. Limit distributions for large Pólya urns. Ann. Appl. Probab.21 (2011) 1–32. Zbl1220.60006MR2759195
  6. [6] H.-H. Chern and H.-K. Hwang. Phase changes in random m -ary search trees and generalized quicksort. Random Structures Algorithms19 (2001) 316–358. Zbl0990.68052MR1871558
  7. [7] R. M. Dudley. Real Analysis and Probability. Cambridge Univ. Press, Cambridge, 2002. Zbl1023.60001MR1932358
  8. [8] R. Durrett and T. Liggett. Fixed points of the smoothing transformation. Z. Wahrsch. verw. Gebiete 64 (1983) 275–301. Zbl0506.60097MR716487
  9. [9] J. A. Fill and N. Kapur. The space requirement of m -ary search trees: Distributional asymptotics for m ≥ 27 . In Proceedings of the 7th Iranian Conference, Tehran, 2004. Available at ArXiv:math.PR/0405144. MR2094243
  10. [10] Y. Guivarc’h. Sur une extension de la notion de loi semi-stable. Ann. Inst. Henri Poincaré Probab. Stat.26 (1990) 261–285. Zbl0703.60012MR1063751
  11. [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. Zbl0638.60027MR925125
  12. [12] S. Janson. Functional limit theorem for multitype branching processes and generalized Pólya urns. Stochastic Process. Appl.110 (2004) 177–245. Zbl1075.60109MR2040966
  13. [13] Q. Liu. Asymptotic properties of supercritical age-dependent branching processes and homogeneous branching random walks. Stochastic Process. Appl.82 (1999) 61–87. Zbl0997.60091MR1695070
  14. [14] Q. Liu. Asymptotic properties and absolute continuity of laws stable by random weighted mean. Stochastic Process. Appl.95 (2001) 83–107. Zbl1058.60068MR1847093
  15. [15] Q. Liu and A. Rouault. Limit theorems for Mandelbrot’s multiplicative cascades. Ann. Appl. Probab.10 (2000) 218–239. Zbl1161.60316MR1765209
  16. [16] H. M. Mahmoud. Evolution of Random Search Trees. Wiley, New York, 1992. Zbl0762.68033MR1140708
  17. [17] J. R. Norris. Markov Chains. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge Univ. Press, Cambridge, 1997. Zbl0873.60043MR1600720
  18. [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). Zbl1096.60007MR2193125
  19. [19] N. Pouyanne. An algebraic approach to Pólya processes. Ann. Inst. Henri Poincaré Probab. Stat.44 (2008) 293–323. Zbl1185.60029MR2446325
  20. [20] U. Rösler. A fixed point theorem for distributions. Stochastic Process. Appl.42 (1992) 195–214. Zbl0761.60015
  21. [21] U. Rösler and L. Rüschendorf. The contraction method for recursive algorithms. Algorithmica29 (2001) 3–33. Zbl0967.68166MR1887296
  22. [22] M. Sharpe. Operator-stable probability distribution on vector groups. Trans. Amer. Math. Soc.136 (1969) 51–65. Zbl0192.53603MR238365

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.