The forward-loop-erased ants walk

Source 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.