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

ESAIM: Probability and Statistics (2010)

- Volume: 14, page 286-298
- ISSN: 1292-8100

## Access Full Article

top## Abstract

top## How to cite

topFekete, Eric. "Branching random walks on binary search trees: convergence of the occupation measure." ESAIM: Probability and Statistics 14 (2010): 286-298. <http://eudml.org/doc/250822>.

@article{Fekete2010,

abstract = {
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.
},

author = {Fekete, Eric},

journal = {ESAIM: Probability and Statistics},

keywords = {Random binary search tree; branching random walk; occupation measure; fragmentation; recursive tree; random binary search tree},

language = {eng},

month = {10},

pages = {286-298},

publisher = {EDP Sciences},

title = {Branching random walks on binary search trees: convergence of the occupation measure},

url = {http://eudml.org/doc/250822},

volume = {14},

year = {2010},

}

TY - JOUR

AU - Fekete, Eric

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

JO - ESAIM: Probability and Statistics

DA - 2010/10//

PB - EDP Sciences

VL - 14

SP - 286

EP - 298

AB -
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.

LA - eng

KW - Random binary search tree; branching random walk; occupation measure; fragmentation; recursive tree; random binary search tree

UR - http://eudml.org/doc/250822

ER -

## References

top- D. Aldous, Tree-based models for random distribution mass. J. Statist. Phys.73 (1993) 625–641. Zbl1102.60318
- J. Bertoin, The asymptotic behavior of fragmentation processes. J. Eur. Math. Soc.5 (2003) 395–416. Zbl1042.60042
- J.D. Biggins, Martingale convergence in the branching random walk. J. Appl. Probab.14 (1977) 25–37. Zbl0356.60053
- P. Billingsley, Probability and measure. Second edition. John Wiley & Sons, New York (1986). Zbl0649.60001
- L. Breiman, Probability. Second edition. SIAM (1992).
- G.G. Brown and B.O. Shubert, On random binary trees. Math. Oper. Res.9 (1985) 43–65. Zbl0529.68035
- P. Chassaing and G. Schaeffer, Random planar lattices and integrated superbrownian excursion. Probab. Theory Relat. Fields128 (2004) 161–212. Zbl1041.60008
- B. Chauvin, T. Klein, J.F. Marckert and A. Rouault, Martingales and profile of binary search trees. Electron. J. Probab.10 (2005) 420–435. Zbl1109.60059
- 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. Zbl1128.60008
- M. Drmota, Profile and height of random binary search trees. J. Iranian Stat. Soc.3 (2004) 117–138.
- M. Fuchs, H.-K. Hwang and R. Neininger, Profiles of random trees: limit theorems for random recursive trees and binary search trees. Available at: (2005). Zbl1106.68083URIhttp://algo.stat.sinica.edu.tw
- S. Janson and J.F. Marckert, Convergence of discrete snakes. J. Theory Probab.18 (2005) 615–645. Zbl1084.60049
- O. Kallenberg, Fundations of Modern Probability. Second edition. Springer-Verlag, New York (2001).
- D.E. Knuth, The art of computer programing, Volume 1: Fundamental algorithms. Second edition. Addison-Wesley, Reading, MA (1997). Zbl0895.68055
- M. Kuba and A. Panholzer, The left-right-imbalance of binary search trees. Available at: (2006). Zbl1118.68052URIhttp://info.tuwien.ac.at/panholzer
- G. Louchard, Exact and asymptotic distributions in digital and binary search trees. RAIRO Theoret. Inform. Appl.21 (1987) 479–496. Zbl0643.68077
- H. Mahmoud, Evolution of Random Search Trees. John Wiley, New York (1992). Zbl0762.68033
- H.M. Mahmoud and R. Neininger, Distribution of distances in random binary search trees. Ann. Appl. Prob.13 (2003) 253–276. Zbl1033.60007
- H.M. Mahmoud and R.T. Smythe, A survey of recursive trees. Theoret. Probab. Math. Statist.51 (1995) 1–27. Zbl0933.05038
- J.-F. Marckert, The rotation correspondence is asymptotically a dilatation. Random Struct. Algorithms24 (2004) 118–132. Zbl1034.05016
- 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. Zbl0977.82022

## NotesEmbed ?

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