The Directed Edge Reinforced Random Walk: The Ant Mill Phenomenon

Abstract

We define here a \textit{directed edge reinforced random walk} on a connected locally finite graph. As the name suggests, this walk keeps track of its past, and gives a bias towards directed edges previously crossed proportional to the exponential of the number of crossings. The model is inspired by the so called \textit{Ant Mill phenomenon}, in which a group of army ants forms a continuously rotating circle until they die of exhaustion. For that reason we refer to the walk defined in this work as the \textit{Ant RW}. Our main result justifies this name. Namely, we will show that on any finite graph which is not a tree, and on ${\mathbb{Z}}^d$ with $d\ge 2$, the Ant RW almost surely gets eventually trapped into some directed circuit which will be followed forever. In the case of~$\mathbb{Z}$ we show that the Ant RW eventually escapes to infinity and satisfies a law of large number with a random limit which we explicitly identify.

In this version we simplify the proof of the main theorem in the finite graph case. We thank Augusto Q. Teixeira for his help