Choice and Bias in Random Walks

5^th May 2023, 13:00 Ashton Lecture Theatre
Dr. John Sylvester
Department of Computer Science, University of Liverpool

Abstract

We will discuss two types of controlled random walks on graphs. In the choice random walk, the controller chooses between two random neighbours at each step. Whereas, in the epsilon-biased random walk the controller instead has a small probability at each step of a free choice of neighbour. We consider the problem of finding optimal strategies for the controller minimising the expected time to hit a given vertex, or visit (cover) all vertices.

We introduce a general framework for boosting the probabilities of rare events using the choice/bias, and use this to show a significant speed-up over the simple random walk for graphs with good expansion properties. We also establish a (partial) complexity dichotomy for making an optimal choice of next step: this is tractable for hitting times but NP-hard for cover times on undirected graphs (PSPACE-complete for directed graphs).

We shall also discuss some new and unpublished results on this topic.

This is joint work with Agelos Georgakopoulos, John Haslegrave, Sam Olesker-Taylor and Thomas Sauerwald.