A degree-biased cutting process for random recursive trees
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909915724906496 |
|---|---|
| author | Eslava, Laura López, Sergio I. Ortiz, Marco L. |
| author_facet | Eslava, Laura López, Sergio I. Ortiz, Marco L. |
| contents | We investigate a degree-biased cutting process on random recursive trees, where each vertex is deleted with probability proportional to its degree. We establish the splitting property and derive the explicit distribution of the number of vertices deleted in each cut. This leads to a recursive formula for Kn, the number of cuts needed to erase a random recursive tree with n vertices. Furthermore, we show that Kn is stochastically dominated by Jn, the number of jumps made by a related walk with a barrier. We prove that Jn converges in distribution to a random variable with a spectrally negative stable distribution. Finally, we examine connections between this cutting procedure and a coalescing process on the set of n elements. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_05168 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A degree-biased cutting process for random recursive trees Eslava, Laura López, Sergio I. Ortiz, Marco L. Probability We investigate a degree-biased cutting process on random recursive trees, where each vertex is deleted with probability proportional to its degree. We establish the splitting property and derive the explicit distribution of the number of vertices deleted in each cut. This leads to a recursive formula for Kn, the number of cuts needed to erase a random recursive tree with n vertices. Furthermore, we show that Kn is stochastically dominated by Jn, the number of jumps made by a related walk with a barrier. We prove that Jn converges in distribution to a random variable with a spectrally negative stable distribution. Finally, we examine connections between this cutting procedure and a coalescing process on the set of n elements. |
| title | A degree-biased cutting process for random recursive trees |
| topic | Probability |
| url | https://arxiv.org/abs/2408.05168 |