A random recursive tree model with doubling events

Jakob E. Björnberg; Cécile Mailler

doi:10.1016/j.spa.2025.104790

A random recursive tree model with doubling events

Jakob E. Björnberg, Cécile Mailler

Chalmers University of Technology and the University of Gothenburg

Research output: Contribution to journal › Article › peer-review

Abstract

We introduce a new model of random tree that grows like a random recursive tree, except at some exceptional "doubling events" when the tree is replaced by two copies of itself attached to a new root. We prove asymptotic results for the size of this tree at large times, its degree distribution, and its height profile. We also prove a lower bound for its height. Because of the doubling events that affect the tree globally, the proofs are all much more intricate than in the case of the random recursive tree in which the growing operation is always local.

Original language	English
Article number	104790
Journal	Stochastic Processes and their Applications
Volume	192
Early online date	21 Oct 2025
DOIs	https://doi.org/10.1016/j.spa.2025.104790
Publication status	E-pub ahead of print - 21 Oct 2025

Acknowledgements

CM would like to thank Jason Schweinsberg for preliminary discussions on the asymptotic behaviour of 𝐵𝑛 as 𝑛 ↑ ∞. We would like to thank Lazare Le Borgne for spotting and correcting a mistake in the proof of Theorem 1.3, and the anonymous referee for reading our paper carefully and making several very helpful comments and suggestions.

Funding

The research of JEB was supported by Vetenskapsrådet , grant 2023-05002, and by Ruth och Nils Erik Stenbäcks stiftelse.

Keywords

math.PR

Access to Document

10.1016/j.spa.2025.104790Licence: CC BY

Cite this

@article{dd29d11380594d31a82de51ac08766ef,

title = "A random recursive tree model with doubling events",

abstract = " We introduce a new model of random tree that grows like a random recursive tree, except at some exceptional {"}doubling events{"} when the tree is replaced by two copies of itself attached to a new root. We prove asymptotic results for the size of this tree at large times, its degree distribution, and its height profile. We also prove a lower bound for its height. Because of the doubling events that affect the tree globally, the proofs are all much more intricate than in the case of the random recursive tree in which the growing operation is always local. ",

keywords = "math.PR",

author = "Bj{\"o}rnberg, \{Jakob E.\} and C{\'e}cile Mailler",

year = "2025",

month = oct,

day = "21",

doi = "10.1016/j.spa.2025.104790",

language = "English",

volume = "192",

journal = "Stochastic Processes and their Applications",

issn = "0304-4149",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - A random recursive tree model with doubling events

AU - Björnberg, Jakob E.

AU - Mailler, Cécile

PY - 2025/10/21

Y1 - 2025/10/21

N2 - We introduce a new model of random tree that grows like a random recursive tree, except at some exceptional "doubling events" when the tree is replaced by two copies of itself attached to a new root. We prove asymptotic results for the size of this tree at large times, its degree distribution, and its height profile. We also prove a lower bound for its height. Because of the doubling events that affect the tree globally, the proofs are all much more intricate than in the case of the random recursive tree in which the growing operation is always local.

AB - We introduce a new model of random tree that grows like a random recursive tree, except at some exceptional "doubling events" when the tree is replaced by two copies of itself attached to a new root. We prove asymptotic results for the size of this tree at large times, its degree distribution, and its height profile. We also prove a lower bound for its height. Because of the doubling events that affect the tree globally, the proofs are all much more intricate than in the case of the random recursive tree in which the growing operation is always local.

KW - math.PR

UR - https://www.scopus.com/pages/publications/105019220954

U2 - 10.1016/j.spa.2025.104790

DO - 10.1016/j.spa.2025.104790

M3 - Article

SN - 0304-4149

VL - 192

JO - Stochastic Processes and their Applications

JF - Stochastic Processes and their Applications

M1 - 104790

ER -

A random recursive tree model with doubling events

Abstract

Acknowledgements

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this