Karine Altisen, Antoine Gerbaud, Stéphane Devismes et Pascal Lafourcade
Comparisons of mean hitting times for tabu random walks on finite graphs (2012)
Comparisons of mean hitting times for tabu random walks on finite graphs (2012)
TR-2012-6.pdf
Keywords: Random walk, tabu list, mean hitting time.
Abstract: A tabu random walk on a graph is a partially self-avoiding random walk to nearest neighbors with finite memory. The walker is endowed with a finite word, called tabu list, whose letters are vertices he has already visited. The policy to insert or remove occurrences of vertices in the tabu list is called update rule. First, we enunciate a necessary and sufficient condition on the update rule that ensures, on all simple, finite and connected graphs, the finiteness of mean hitting times of each vertex. Then, we describe, on large classes of graph, the update rules having the smallest mean hitting times. Finally, we compare mean hitting times for three particular collections update rules.
