Tree builder random walk

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. That is, the walker and the graph on which it moves mutually influence each other. At discrete time units, right before stepping, the walker adds a random number (possibly zero) leaves to its current position. We assume that the number of leaves at each time unit are independent, but we do not assume that they are identically distributed, resulting thus in a time in-homogeneous setting. Properties of the walk (transience/recurrence, getting stuck) as well as the structure of the generated random trees (limiting degree, distribution, maximal degree etc.) are discussed. A coupling with the well-known preferential attachment model of Barabási and Albert turns out to be useful in the appropriate regime. This is joint work with R. Ribeiro (Denver/Rio de Janeiro), G. Iacobelli (Rio de Janeiro) and G. Pete (Budapest).