Structural results for the Tree Builder Random Walk

2023/11/30 by Engländer, Janos, Iacobelli, Giulio, Pete, Gábor +1 · 1 citation
#05C80 #05C81 #60F99 #60J05 #Chemical Physics (physics.chem-ph) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Physics and Society (physics.soc-ph) #Probability (math.PR)

paper · doi:10.48550/arxiv.2311.18734

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 \asymp 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.

Cited by

• Evolution of recursive trees with limited memory

Related

• Recurrence, transience and degree distribution for the Tree Builder Random Walk
• Tree Builder Random Walk: recurrence, transience and ballisticity
• Renewal structure of the Tree Builder Random Walk
• Random friend trees
• Transient and Slim versus Recurrent and Fat: Random Walks and the Trees they Grow