Seminar Event Detail

What is... ?

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

Event Organizer:     


Edit this event (login required).
Add new event (login required).
For access requests and instructions, contact

Back to previous page
Back to UM Math seminars/events page.