Paperlane

no. 5 · Friday 30 October 2026

Multi-excited random walks on general trees

Jack Mills and Tuan-Minh Nguyen

math.PR · 39 pp

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.

comments
39 pages
fields
Probability, Mathematical Physics
pdf ↗ page arXiv:2610.40084 ↗