University of Cambridge > > The Archimedeans > The Power of Two Choices in Random Walks

The Power of Two Choices in Random Walks

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

  • UserSpeaker to be confirmed
  • ClockTuesday 17 May 2022, 18:00-19:00
  • HouseMR2 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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity