Structural results for the Tree Builder Random Walk
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929617443487744 |
|---|---|
| author | Engländer, Janos Iacobelli, Giulio Pete, Gábor Ribeiro, Rodrigo |
| author_facet | Engländer, Janos Iacobelli, Giulio Pete, Gábor Ribeiro, Rodrigo |
| contents | We study the Tree Builder Random Walk: a randomly growing tree, built by a walker as she is walking around the tree. Namely, at each time $n$, she adds a leaf to her current vertex with probability $p_n \asymp n^{-γ}$, $γ\in (2/3,1]$, then moves to a uniform random neighbor on the possibly modified tree. We show that the tree process at its growth times, after a random finite number of steps, can be coupled to be identical to the Barabási-Albert preferential attachment tree model.
Thus, our TBRW-model is a local dynamics giving rise to the BA-model. The coupling also implies that many properties known for the BA-model, such as diameter and degree distribution, can be directly transferred to our TBRW-model, extending previous results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_18734 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Structural results for the Tree Builder Random Walk Engländer, Janos Iacobelli, Giulio Pete, Gábor Ribeiro, Rodrigo Probability Data Structures and Algorithms Chemical Physics Physics and Society 05C81, 05C80, 60F99, 60J05 We study the Tree Builder Random Walk: a randomly growing tree, built by a walker as she is walking around the tree. Namely, at each time $n$, she adds a leaf to her current vertex with probability $p_n \asymp n^{-γ}$, $γ\in (2/3,1]$, then moves to a uniform random neighbor on the possibly modified tree. We show that the tree process at its growth times, after a random finite number of steps, can be coupled to be identical to the Barabási-Albert preferential attachment tree model. Thus, our TBRW-model is a local dynamics giving rise to the BA-model. The coupling also implies that many properties known for the BA-model, such as diameter and degree distribution, can be directly transferred to our TBRW-model, extending previous results. |
| title | Structural results for the Tree Builder Random Walk |
| topic | Probability Data Structures and Algorithms Chemical Physics Physics and Society 05C81, 05C80, 60F99, 60J05 |
| url | https://arxiv.org/abs/2311.18734 |