The Directed Edge Reinforced Random Walk: The Ant Mill Phenomenon

We define here a $\mathit{\text{directed}}\mathit{\text{edge}}\mathit{\text{reinforced}}\mathit{\text{random}}\mathit{\text{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 $\mathit{\text{Ant}}\mathit{\text{Mill}}\mathit{\text{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 $\mathit{\text{Ant}}\mathit{\text{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.