The forward-loop-erased ants walk
Abstract
In this paper, we study a new variant of the ants walk: a model of reinforced random walks for the phenomenon of a colony of ants being able to find the shortest path between their nest and a source of food. In this model, the nest and the source of food are two distinguished nodes in a finite graph. The ants perform successive random walks on this graph, started at the nest and stopped when they first hit the food source; the transition probabilities of each random walk depends on the trajectories of the previous ants, through some edge-weights that represent the amount pheromones deposited on each edge. In our new variant of the model, the ant (1) forgets loops made on the way to the food as soon as they are made, and (2) comes back to the nest following this loop-erased version of its forward trajectory, and deposits pheromone on the edges it crosses by doing so (i.e. adds one to these edges' weights). We say that the ants "find the shortest path" if, almost surely as the number of ants tends to infinity, the proportion of ants that travel along a graph-geodesic path from the nest to the food tends to one and the proportion of ants that travel along the remaining edges tends to zero. We are able to prove that this new variant of the model finds the shortest path when the graph distance between the nest and the source is at most 2. The strength of our result is that there is no other assumption on the shape of the graph. We prove this result using stochastic approximation theory, the electrical network method for random walks on weighted graphs, and the theory of weighted uniform spanning trees (WUSTs). In particular, the link with WUSTs is unique to the model studied in this paper due to the way the ant erases loops on the outward journey.
Related
- An explicit lower bound for the growth exponent of three-dimensional loop-erased random walk
- Characterization and scaling limit of three-dimensional loop-erased random walk and random-walk loop-catchers
- The boosted loop-erased random walk
- The Cotton Line: Testing the Institutional Persistence of an Erased Colonial Land-Tenure Boundary Across Vidarbha's Agrarian and Vegetation Geography
- On the critical branching random walk I: branching capacity and visiting probability
BibTeX
@misc{armfield2026forwardlooperased,
title = {{The forward-loop-erased ants walk}},
author = {Wilfred Armfield and Cécile Mailler},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18453},
eprint = {2610.18453},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18453},
}
RIS
TY - UNPB
TI - The forward-loop-erased ants walk
AU - Wilfred Armfield
AU - Cécile Mailler
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.18453
UR - https://arxiv.org/abs/2610.18453
AB - In this paper, we study a new variant of the ants walk: a model of reinforced random walks for the phenomenon of a colony of ants being able to find the shortest path between their nest and a source of food. In this model, the nest and the source of food are two distinguished nodes in a finite graph. The ants perform successive random walks on this graph, started at the nest and stopped when they first hit the food source; the transition probabilities of each random walk depends on the trajectories of the previous ants, through some edge-weights that represent the amount pheromones deposited on each edge. In our new variant of the model, the ant (1) forgets loops made on the way to the food as soon as they are made, and (2) comes back to the nest following this loop-erased version of its forward trajectory, and deposits pheromone on the edges it crosses by doing so (i.e. adds one to these edges' weights). We say that the ants "find the shortest path" if, almost surely as the number of ants tends to infinity, the proportion of ants that travel along a graph-geodesic path from the nest to the food tends to one and the proportion of ants that travel along the remaining edges tends to zero. We are able to prove that this new variant of the model finds the shortest path when the graph distance between the nest and the source is at most 2. The strength of our result is that there is no other assumption on the shape of the graph. We prove this result using stochastic approximation theory, the electrical network method for random walks on weighted graphs, and the theory of weighted uniform spanning trees (WUSTs). In particular, the link with WUSTs is unique to the model studied in this paper due to the way the ant erases loops on the outward journey.
ER -