Document Open Access Logo

Fragmentation Processes Derived from Conditioned Stable Galton-Watson Trees

Authors Gabriel Berzunza Ojeda , Cecilia Holmgren

PDF
Thumbnail PDF

File

LIPIcs.AofA.2022.3.pdf
  • Filesize: 0.76 MB
  • 14 pages

Document Identifiers

Author Details

Gabriel Berzunza Ojeda
  • Department of Mathematical Sciences, University of Liverpool, United Kingdom
Cecilia Holmgren
  • Department of Mathematics, Uppsala University, Sweden

Funding

This work was supported by the Knut and Alice Wallenberg Foundation, a grant from the Swedish Research Council and The Swedish Foundations' starting grant from Ragnar Söderbergs Foundation.

Cite AsGet BibTex

Gabriel Berzunza Ojeda and Cecilia Holmgren. Fragmentation Processes Derived from Conditioned Stable Galton-Watson Trees. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.AofA.2022.3

Abstract

We study the fragmentation process obtained by deleting randomly chosen edges from a critical Galton-Watson tree 𝐭_n conditioned on having n vertices, whose offspring distribution belongs to the domain of attraction of a stable law of index α ∈ (1,2]. This fragmentation process is analogous to that introduced in the works of Aldous, Evans and Pitman (1998), who considered the case of Cayley trees. Our main result establishes that, after rescaling, the fragmentation process of 𝐭_n converges as n → ∞ to the fragmentation process obtained by cutting-down proportional to the length on the skeleton of an α-stable Lévy tree of index α ∈ (1,2]. We further establish that the latter can be constructed by considering the partitions of the unit interval induced by the normalized α-stable Lévy excursion with a deterministic drift studied by Miermont (2001). In particular, this extends the result of Bertoin (2000) on the fragmentation process of the Brownian CRT.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Probabilistic algorithms
Keywords
  • Additive coalescent
  • fragmentation
  • Galton-Watson trees
  • spectrally positive stable Lévy processes
  • stable Lévy tree
  • Prim’s algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Romain Abraham and Laurent Serlet. Poisson snake and fragmentation. Electron. J. Probab., 7:no. 17, 15, 2002. URL: https://doi.org/10.1214/EJP.v7-116.
  2. David Aldous. Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab., 25(2):812-854, 1997. URL: https://doi.org/10.1214/aop/1024404421.
  3. David Aldous and Jim Pitman. The standard additive coalescent. Ann. Probab., 26(4):1703-1726, 1998. URL: https://doi.org/10.1214/aop/1022855879.
  4. David Aldous and Jim Pitman. Inhomogeneous continuum random trees and the entrance boundary of the additive coalescent. Probab. Theory Related Fields, 118(4):455-482, 2000. URL: https://doi.org/10.1007/PL00008751.
  5. Jean Bertoin. Lévy processes, volume 121 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 1996. Google Scholar
  6. Jean Bertoin. A fragmentation process connected to Brownian motion. Probab. Theory Related Fields, 117(2):289-301, 2000. URL: https://doi.org/10.1007/s004400050008.
  7. Jean Bertoin. Eternal additive coalescents and certain bridges with exchangeable increments. Ann. Probab., 29(1):344-360, 2001. URL: https://doi.org/10.1214/aop/1008956333.
  8. Jean Bertoin. Self-similar fragmentations. Ann. Inst. H. Poincaré Probab. Statist., 38(3):319-340, 2002. URL: https://doi.org/10.1016/S0246-0203(00)01073-6.
  9. Jean Bertoin. Almost giant clusters for percolation on large trees with logarithmic heights. J. Appl. Probab., 50(3):603-611, 2013. URL: https://doi.org/10.1239/jap/1378401225.
  10. Jean Bertoin and Grégory Miermont. Asymptotics in Knuth’s parking problem for caravans. Random Structures Algorithms, 29(1):38-55, 2006. URL: https://doi.org/10.1002/rsa.20092.
  11. Gabriel Berzunza Ojeda and Cecilia Holmgren. Invariance principle for fragmentation processes derived from conditioned stable Galton-Watson trees. arXiv e-prints, page arXiv:2010.07880, October 2020. URL: http://arxiv.org/abs/2010.07880.
  12. Patrick Billingsley. Convergence of probability measures. Wiley Series in Probability and Statistics: Probability and Statistics. John Wiley & Sons, Inc., New York, second edition, 1999. A Wiley-Interscience Publication. URL: https://doi.org/10.1002/9780470316962.
  13. Nicolas Broutin and Jean-François Marckert. A new encoding of coalescent processes: applications to the additive and multiplicative cases. Probab. Theory Related Fields, 166(1-2):515-552, 2016. URL: https://doi.org/10.1007/s00440-015-0665-1.
  14. P. Chassaing and G. Louchard. Phase transition for parking blocks, Brownian excursion and coalescence. Random Structures Algorithms, 21(1):76-119, 2002. URL: https://doi.org/10.1002/rsa.10039.
  15. Philippe Chassaing and Svante Janson. A Vervaat-like path transformation for the reflected Brownian bridge conditioned on its local time at 0. Ann. Probab., 29(4):1755-1779, 2001. URL: https://doi.org/10.1214/aop/1015345771.
  16. L. Chaumont. Excursion normalisée, méandre et pont pour les processus de Lévy stables. Bull. Sci. Math., 121(5):377-403, 1997. Google Scholar
  17. Thomas Duquesne. A limit theorem for the contour process of conditioned Galton-Watson trees. Ann. Probab., 31(2):996-1027, 2003. URL: https://doi.org/10.1214/aop/1048516543.
  18. Thomas Duquesne and Jean-François Le Gall. Random trees, Lévy processes and spatial branching processes. Astérisque, 281:vi+147, 2002. Google Scholar
  19. Steven N. Evans and Jim Pitman. Construction of Markovian coalescents. Ann. Inst. H. Poincaré Probab. Statist., 34(3):339-383, 1998. URL: https://doi.org/10.1016/S0246-0203(98)80015-0.
  20. William Feller. An introduction to probability theory and its applications. Vol. II. Second edition. John Wiley & Sons, Inc., New York-London-Sydney, 1971. Google Scholar
  21. Jean Jacod and Albert N. Shiryaev. Limit theorems for stochastic processes, volume 288 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, second edition, 2003. URL: https://doi.org/10.1007/978-3-662-05265-5.
  22. Olav Kallenberg. Foundations of modern probability. Probability and its Applications (New York). Springer-Verlag, New York, second edition, 2002. URL: https://doi.org/10.1007/978-1-4757-4015-8.
  23. Jean-François Le Gall. Random trees and applications. Probab. Surv., 2:245-311, 2005. URL: https://doi.org/10.1214/154957805100000140.
  24. Jean-François Marckert and Minmin Wang. A new combinatorial representation of the additive coalescent. Random Structures Algorithms, 54(2):340-370, 2019. URL: https://doi.org/10.1002/rsa.20775.
  25. Grégory Miermont. Ordered additive coalescent and fragmentations associated to Levy processes with no positive jumps. Electron. J. Probab., 6:no. 14, 33, 2001. URL: https://doi.org/10.1214/EJP.v6-87.
  26. Grégory Miermont. Self-similar fragmentations derived from the stable tree. II. Splitting at nodes. Probab. Theory Related Fields, 131(3):341-375, 2005. URL: https://doi.org/10.1007/s00440-004-0373-8.
  27. J. Neveu. Arbres et processus de Galton-Watson. Ann. Inst. H. Poincaré Probab. Statist., 22(2):199-207, 1986. URL: http://www.numdam.org/item?id=AIHPB_1986__22_2_199_0.
  28. Jim Pitman. Coalescent random forests. J. Combin. Theory Ser. A, 85(2):165-193, 1999. URL: https://doi.org/10.1006/jcta.1998.2919.
  29. R. C. Prim. Shortest connection networks and some generalizations. The Bell System Technical Journal, 36(6):1389-1401, 1957. Google Scholar
  30. Paul Thévenin. A geometric representation of fragmentation processes on stable trees. The Annals of Probability, 49(5):2416-2476, 2021. URL: https://doi.org/10.1214/21-AOP1512.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact