Choice and Bias in Random Walks

9^th December 2020, 14:00
John Sylvester
University of Cambridge

Abstract

We consider two types of controlled random walks on graphs.
In the choice random walk, the controller chooses between two random
neighbours at each step; in the epsilon-biased random walk the controller
instead has a small probability at each step of a free choice of neighbour.
The former was previously studied empirically by Avin and Krishnamachari
(2008). The latter was introduced for a fixed set of biases by Azar et al.
(1996), but we extend it to allow biases to depend on the previous walk.
In particular, we consider finding the problem of finding optimal strategies
for the controller minimising the expected time to hit a given vertex or visit
(cover) all vertices. Using a general framework for boosting the probabilities
of rare events, we show a significant speed up over the simple random
walk for graphs with good expansion properties. We also establish a complexity
dichotomy for making optimal choices, which are tractable for hitting times but
NP-hard for cover times on undirected graphs (and PSPACE-complete for directed graphs).
This is joint work with Agelos Georgakopoulos, John Haslegrave and Thomas Sauerwald.