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

Eric Fekete

ESAIM: Probability and Statistics (2010)

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

Abstract

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

How to cite

top

Fekete, 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
  1. D. Aldous, Tree-based models for random distribution mass. J. Statist. Phys.73 (1993) 625–641.  
  2. J. Bertoin, The asymptotic behavior of fragmentation processes. J. Eur. Math. Soc.5 (2003) 395–416.  
  3. J.D. Biggins, Martingale convergence in the branching random walk. J. Appl. Probab.14 (1977) 25–37.  
  4. P. Billingsley, Probability and measure. Second edition. John Wiley & Sons, New York (1986).  
  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.  
  7. P. Chassaing and G. Schaeffer, Random planar lattices and integrated superbrownian excursion. Probab. Theory Relat. Fields128 (2004) 161–212.  
  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.  
  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.  
  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: (2005).  URIhttp://algo.stat.sinica.edu.tw
  12. S. Janson and J.F. Marckert, Convergence of discrete snakes. J. Theory Probab.18 (2005) 615–645.  
  13. O. Kallenberg, Fundations of Modern Probability. Second edition. Springer-Verlag, New York (2001).  
  14. D.E. Knuth, The art of computer programing, Volume 1: Fundamental algorithms. Second edition. Addison-Wesley, Reading, MA (1997).  
  15. M. Kuba and A. Panholzer, The left-right-imbalance of binary search trees. Available at: (2006).  URIhttp://info.tuwien.ac.at/panholzer
  16. G. Louchard, Exact and asymptotic distributions in digital and binary search trees. RAIRO Theoret. Inform. Appl.21 (1987) 479–496.  
  17. H. Mahmoud, Evolution of Random Search Trees. John Wiley, New York (1992).  
  18. H.M. Mahmoud and R. Neininger, Distribution of distances in random binary search trees. Ann. Appl. Prob.13 (2003) 253–276.  
  19. H.M. Mahmoud and R.T. Smythe, A survey of recursive trees. Theoret. Probab. Math. Statist.51 (1995) 1–27.  
  20. J.-F. Marckert, The rotation correspondence is asymptotically a dilatation. Random Struct. Algorithms24 (2004) 118–132.  
  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.  

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.