STRUCTURAL RESULTS FOR THE TREE BUILDER RANDOM WALK

• 成果类型: Article
• 署名作者: Englander, Janos; Iacobelli, Giulio; Pete, Gabor; Ribeiro, Rodrigo
• 署名单位: University of Colorado System; University of Colorado Boulder; Universidade Federal do Rio de Janeiro; HUN-REN; HUN-REN Alfred Renyi Institute of Mathematics; Budapest University of Technology & Economics; University of Denver
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/24-AAP2128
• 发表日期: 2025
• 页码: 822-857
• 关键词: NETWORKS; connectivity; POWER

摘要

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-gamma , gamma is an element of ( 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 & aacute;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.