Choice and bias in random walks.

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. We consider particularly the goals of minimising hitting times and cover time. 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. This is joint work with Agelos Georgakopoulos, Thomas Sauerwald and John Sylvester.