Abstract

A random walk on a graph starts at an arbitrary vertex, and at each step moves to a neighbouring vertex chosen at random. Random walks (Markov chains) appear in many areas including physics (heat equation), biology (Brownian motion), and computer science (randomised algorithms).

In this talk, we consider two types of controlled random walks on graphs. In the ``choice random walk’’, at each step the controller chooses between two given random neighbours. The second process is a ``biased random walk’’, where the controller has a small probability at each step of a free choice of neighbour. The goal of the controller can be, for example, to minimise the expected time to visit a vertex (or all vertices), or to maximise the frequency of returns to a vertex. We discuss several strategies for both processes, and analyse them on some basic graphs.