On a random walk that grows its own tree
Authors:
- Daniel FigueiredoDFDaniel Figueiredo
- Giulio IacobelliGIGiulio Iacobelli
- Roberto OliveiraRORoberto Oliveira
- Bruce ReedBRBruce Reed
- Rodrigo RibeiroRRRodrigo Ribeiro
Open Access
- 1 January 2021
- journal article
- research article
- Published by Institute of Mathematical Statistics in Electronic Journal of Probability
- Vol. 26 (none) , 1-40
Abstract
Random walks on dynamic graphs have received increasingly more attention from different academic communities over the last decade. Despite the relatively large literature, little is known about random walks that construct the graph where they walk while moving around. In this paper we study one of the simplest conceivable discrete time models of this kind, which works as follows: before every walker step, with probability $p$ a new leaf is added to the vertex currently occupied by the walker. The model grows trees and we call it the Bernoulli Growth Random Walk (BGRW). We show that the BGRW walker is transient and has a well-defined linear speed $c(p)>0$ for any $0<p\leq 1$. Moreover, we show that the tree as seen by the walker converges (in a suitable sense) to a random tree that is one-ended. Some natural open problems about this tree and variants of our model are collected at the end of the paper.
Keywords
This publication has 17 references indexed in Scilit:
- Growing Networks Through Random Walks Without Restarts2016
- Transience of Edge-Reinforced Random WalkCommunications in Mathematical Physics, 2015
- Random walks on dynamical percolation: mixing times, mean squared displacement and hitting timesProbability Theory and Related Fields, 2014
- Random walk attachment graphsElectronic Communications in Probability, 2013
- Characterizing continuous time random walks on time varying graphsACM SIGMETRICS Performance Evaluation Review, 2012
- On the transience of processes defined on Galton–Watson treesThe Annals of Probability, 2006
- Scale-free networks generated by random walkersPhysica A: Statistical Mechanics and its Applications, 2004
- The point of view of the particle on the law of large numbers for random walks in a mixing random environmentThe Annals of Probability, 2003
- Once edge-reinforced random walk on a treeProbability Theory and Related Fields, 2002
- Ergodic theory on Galton—Watson trees: speed of random walk and dimension of harmonic measureErgodic Theory and Dynamical Systems, 1995