Branching random walks on binary search trees : convergence of the occupation measure

Fekete, Eric

ESAIM: Probability and Statistics, Tome 14 (2010), pp. 286-298.

We consider branching random walks with binary search trees as underlying trees. We show that the occupation measure of the branching random walk, up to some scaling factors, converges weakly to a deterministic measure. The limit depends on the stable law whose domain of attraction contains the law of the increments. The existence of such stable law is our fundamental hypothesis. As a consequence, using a one-to-one correspondence between binary trees and plane trees, we give a description of the asymptotics of the profile of recursive trees. The main result is also applied to the study of the size of the fragments of some homogeneous fragmentations.

Classification : 60F05, 60G50, 68W40, 60J80, 05C05
Mots clés : random binary search tree, branching random walk, occupation measure, fragmentation, recursive tree

[1] D. Aldous, Tree-based models for random distribution mass. J. Statist. Phys. 73 (1993) 625-641. | Zbl

[2] J. Bertoin, The asymptotic behavior of fragmentation processes. J. Eur. Math. Soc. 5 (2003) 395-416. | EuDML | Zbl

[3] J.D. Biggins, Martingale convergence in the branching random walk. J. Appl. Probab. 14 (1977) 25-37. | Zbl

[4] P. Billingsley, Probability and measure. Second edition. John Wiley & Sons, New York (1986). | Zbl

[5] L. Breiman, Probability. Second edition. SIAM (1992).

[6] G.G. Brown and B.O. Shubert, On random binary trees. Math. Oper. Res. 9 (1985) 43-65. | Zbl

[7] P. Chassaing and G. Schaeffer, Random planar lattices and integrated superbrownian excursion. Probab. Theory Relat. Fields 128 (2004) 161-212. | Zbl

[8] B. Chauvin, T. Klein, J.F. Marckert and A. Rouault, Martingales and profile of binary search trees. Electron. J. Probab. 10 (2005) 420-435. | EuDML | Zbl

[9] L. Devroye and H.K. Hwang, Width and more of the profile for random trees of logarithmic height. Ann. Appl. Probab. 16 (2006) 886-918. | Zbl

[10] M. Drmota, Profile and height of random binary search trees. J. Iranian Stat. Soc. 3 (2004) 117-138.

[11] M. Fuchs, H.-K. Hwang and R. Neininger, Profiles of random trees: limit theorems for random recursive trees and binary search trees. Available at: http://algo.stat.sinica.edu.tw (2005). | Zbl

[12] S. Janson and J.F. Marckert, Convergence of discrete snakes. J. Theory Probab. 18 (2005) 615-645. | Zbl

[13] O. Kallenberg, Fundations of Modern Probability. Second edition. Springer-Verlag, New York (2001). | Zbl

[14] D.E. Knuth, The art of computer programing, Volume 1: Fundamental algorithms. Second edition. Addison-Wesley, Reading, MA (1997). | Zbl

[15] M. Kuba and A. Panholzer, The left-right-imbalance of binary search trees. Available at: http://info.tuwien.ac.at/panholzer (2006). | Zbl

[16] G. Louchard, Exact and asymptotic distributions in digital and binary search trees. RAIRO Theoret. Inform. Appl. 21 (1987) 479-496. | Numdam | Zbl

[17] H. Mahmoud, Evolution of Random Search Trees. John Wiley, New York (1992). | Zbl

[18] H.M. Mahmoud and R. Neininger, Distribution of distances in random binary search trees. Ann. Appl. Prob. 13 (2003) 253-276. | Zbl

[19] H.M. Mahmoud and R.T. Smythe, A survey of recursive trees. Theoret. Probab. Math. Statist. 51 (1995) 1-27. | Zbl

[20] J.-F. Marckert, The rotation correspondence is asymptotically a dilatation. Random Struct. Algorithms 24 (2004) 118-132. | Zbl

[21] G. Slade and T. Hara, The scaling limit of the incipient infinite cluster in high-dimensional percolation. II. Integrated super-brownian excursion. J. Math. Phys. 41 (2000) 1244-1293. | Zbl