Tree builder random walks

ESB 4127

We investigate a self-interacting random walk, in a dynamically evolving environment, which is a random tree built by the walker itself, as it walks around.

At time $n=1,2,\dots$, right before stepping, the walker adds a random number (possibly zero) $Z_n$ of leaves to its current position. We assume that the $Z_n$'s are independent but we do not assume that they are identically distributed, resulting thus in a time in-homogeneous setting.

The properties of the walk (transience/recurrence, getting stuck) as well as the structure of the generated random trees  are discussed (limiting degree distribution, maximal degree etc.).

 A coupling with the well-known preferential attachment model of Barabasi and Albert turns out to be useful in the appropriate regime.

This is joint work with R. Ribeiro (Denver), G. Iacobelli (Rio de Janeiro) and G. Pete (Budapest).