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