|Date: Tuesday, October 30, 2012
Location: 3096 East Hall (2:10 PM to 3:00 PM)
Title: What is ... the mixing time and the cover time for random walk on a graph?
Abstract: Consider a simple random walk on a finite graph. The mixing time is the time it takes the walk to reach a position that is approximately independent of the starting point; the cover time is the expected time it takes the walk to visit all vertices. These two quantities have been studied intensively by combinatorialists, computer scientists and probabilists; the mixing time arises in statistical physics as well. Applications of mixing times range from random sampling and card shuffling, to understanding convergence to equilibrium in the Ising model. It is closely related to expansion and eigenvalues. Cover times arise in algorithms to determine connectivity in networks.
Besides giving an introduction to these topics, I will describe the open problem of understanding which random walks exhibit “cutoff”, a sharp transition to stationarity.
Speaker: Yuval Peres
Institution: Microsoft Research Redmond