Structural results for the Tree Builder Random Walk
Preprint
Abstract
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=n^{-\gamma}$, $\gamma\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\'asi-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.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Recurrence, transience and degree distribution for the Tree Builder Random WalkAnnales de l'Institut Henri Poincaré, Probabilités et Statistiques, 2025
- Theory of chain walking catalysis: From disordered dendrimers to dendritic bottle-brushesThe Journal of Chemical Physics, 2022
- On a random walk that grows its own treeElectronic Journal of Probability, 2021
- Estimating graph parameters via random walks with restarts2018
- The power of averaging at two consecutive time steps: Proof of a mixing conjecture by Aldous and FillAnnales de l'Institut Henri Poincaré, Probabilités et Statistiques, 2017
- The degree sequence of a scale‐free random graph processRandom Structures & Algorithms, 2001
- Emergence of Scaling in Random NetworksScience, 1999
- Note on the heights of random recursive trees and random m‐ary search treesRandom Structures & Algorithms, 1994
- Geometric Bounds for Eigenvalues of Markov ChainsThe Annals of Applied Probability, 1991
- Bounds on the cover timeJournal of Theoretical Probability, 1989