Tree builder random walk: recurrence, transience and ballisticity

DOI10.3150/21-BEJ1337MaRDI QIDQ2073207zbMATH OpenOpenAlexFDO

Authors Giulio Iacobelli, Rodrigo Ribeiro, Leonel Zuaznábar, Glauco Valle

Publication date 1 February 2022

Published in Bernoulli (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.07616, https://projecteuclid.org/journals/bernoulli/volume-28/issue-1/Tree-builder-random-walk-Recurrence-transience-and-ballisticity/10.3150/21-BEJ1337.full

zbMATH Keywords

ballisticityrandom environmentrandom treesrandom walksrecurrencetransience

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Processes in random environments (60K37)

Abstract: The Tree Builder Random Walk is a special random walk that evolves on trees whose size increases with time, randomly and depending upon the walker. After every s steps of the walker, a random number of vertices are added to the tree and attached to the current position of the walker. These processes share similarities with other important classes of markovian and non-markovian random walks presenting a large variety of behaviors according to parameters specifications. We show that for a large and most significant class of tree builder random walks, the process is either null recurrent or transient. If s is odd, the walker is ballistic and thus transient. If s is even, the walker's behavior can be explained from local properties of the growing tree and it can be either null recurrent or it gets trapped on some limited part of the growing tree.

Review text

The authors considered a tree builder random walk (TBRW), which evolves on trees whose size increases randomly with time. Namely, given a parameter \(s\in \mathbb N\) of the model, after every \(s\) transitions of the walker a random number of vertices are added to the tree and attached to the current position of the random walk. It proved that for a large and most significant class of TBRWs, the process is either null recurrent or transient. Moreover, if \(s\) is odd then the walker is ballistic, thus transient; if \(s\) is even then the walker's behavior depends from local properties of the growing tree: it can be either null recurrent or it gets trapped on some limited part of the growing tree.

Recommendations

• Recurrence and transience of a multi-excited random walk on a regular tree
• scientific article; zbMATH DE number 3949430
• Random walks and trees
• Random walks and dimensions of random trees
• Random walk on periodic trees
• On the transience and recurrence of Lamperti's random walk on Galton-Watson trees
• scientific article; zbMATH DE number 1123792
• scientific article; zbMATH DE number 1192303
• Simple random walks on trees

Cites work

• A law of large numbers for random walks in random environment
• A survey of random processes with reinforcement
• Biased random walks on Galton-Watson trees
• Ellipticity criteria for ballistic behavior of random walks in random environment
• Excited random walks: results, methods, open problems
• scientific article; zbMATH DE number 2070282 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Local trapping for elliptic random walks in random environments in \(\mathbb {Z}^d\)
• Mixing times of random walks on dynamic configuration models
• Moderate Deviations for I.I.D. Random Variables
• On a class of transient random walks in random environment
• On a random walk that grows its own tree
• Phase transition in reinforced random walk and RWRE on trees
• Probability. Theory and examples.
• Random graph dynamics
• Random graphs and complex networks. Volume 1
• Random walks on dynamical percolation: mixing times, mean squared displacement and hitting times
• Reinforced random walk
• Sharp ellipticity conditions for ballistic behavior of random walks in random environment
• Transience of edge-reinforced random walk
• Transient and slim versus recurrent and fat: random walks and the trees they grow
• Tree builder random walk: recurrence, transience and ballisticity
• Walking within growing domains: recurrence versus transience

Cited in

(8)

• On a random walk that grows its own tree
• Tree builder random walk: recurrence, transience and ballisticity
• Transient and slim versus recurrent and fat: random walks and the trees they grow
• Erratum to: ``Tree builder random walk: recurrence, transience and ballisticity
• A phase transition for the biased tree-builder random walk
• Recurrence, transience and degree distribution for the tree builder random walk
• Renewal structure of the tree builder random walk
• Structural results for the tree builder random walk

This page was built for publication: Tree builder random walk: recurrence, transience and ballisticity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2073207)