Structural results for the tree builder random walk
Authors:
- 1 April 2025
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 35 (2) , 822-857
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 pn=n−γ, γ∈(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.Keywords
All Related Versions
This publication has 50 references indexed in Scilit:
- Co-evolving dynamic networksProbability Theory and Related Fields, 2024
- Growing Networks Through Random Walks Without Restarts2016
- Random trees and general branching processesRandom Structures & Algorithms, 2006
- Levels of a scale‐free treeRandom Structures & Algorithms, 2005
- Mathematical results on scale‐free random graphs2002
- The degree sequence of a scale‐free random graph processRandom Structures & Algorithms, 2001
- The true self-repelling motionProbability Theory and Related Fields, 1998
- Concentration1998
- Note on the heights of random recursive trees and random m‐ary search treesRandom Structures & Algorithms, 1994
- Bounds on the cover timeJournal of Theoretical Probability, 1989