BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:The Power of Two Choices in Random Walks - Speaker to be confirmed
DTSTART:20220517T170000Z
DTEND:20220517T180000Z
UID:TALK174659@talks.cam.ac.uk
CONTACT:106940
DESCRIPTION:A random walk on a graph starts at an arbitrary vertex\, and a
 t each step moves to a neighbouring vertex chosen at random. Random walks 
 (Markov chains) appear in many areas including physics (heat equation)\, b
 iology (Brownian motion)\, and computer science (randomised algorithms). \
 n \nIn this talk\, we consider two types of controlled random walks on gra
 phs. In the ``choice random walk''\, at each step the controller chooses b
 etween two given random neighbours. The second process is a ``biased rando
 m 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 t
 o maximise the frequency of returns to a vertex. We discuss several strate
 gies for both processes\, and analyse them on some basic graphs.
LOCATION:MR2 in the CMS
END:VEVENT
END:VCALENDAR