The Power of Two Choices in Random Walks

Add to your list(s) Download to your calendar using vCal

• Speaker to be confirmed
• Tuesday 17 May 2022, 18:00-19:00
• MR2 in the CMS.

If you have a question about this talk, please contact zl474.

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.

This talk is part of the The Archimedeans series.

This talk is included in these lists:

• MR2 in the CMS
• The Archimedeans
• ob366-ai4er

Note that ex-directory lists are not shown.