Multi-excited random walks on general trees

Abstract

We study multi-excited random walks on infinite locally finite trees. The model is described by placing a stack of ``cookies'' at each vertex, with one cookie consumed on each successive visit. As long as cookies remain, the walk is in an excited regime and makes nearest-neighbour steps according to a prescribed sequence of biases. Once the stack is exhausted, the walk is in a non-excited regime and moves uniformly among the neighbouring vertices. The model is closely connected to foraging ecology, where repeated visits to a location can deplete local resources and thereby influence the attractiveness of that location for future visits. We prove that the process exhibits a sharp phase transition between recurrence and transience. The critical threshold is determined by the branching-ruin number of the tree, which is equal to the Hausdorff dimension of the tree's boundary under a suitable metric. Our result substantially extends Zerner's recurrence-transience criterion for multi-excited random walks on $\mathbb Z$ [Probab. Theory Related Fields 133 (2005)] to general trees.