Talk by Sharad Goel (Stanford University)

Date and Time: Thursday, October 20, 2005, 10:00 AM in AP&M 6218.

Title: Estimating mixing times via the spectral profile

Abstract: Given 52 playing cards, how many shuffles does it take to approximately randomize the deck? More generally, how long does it take a finite Markov chain to get close to its stationary distribution? In this talk, I'll introduce the spectral profile as a tool for proving upper and lower bounds on convergence rates. This approach extends the commonly used spectral gap method, and allows us to recover and refine previous conductance-based estimates of mixing time. I will illustrate how the spectral profile technique is applied in several models, including groups with moderate growth, the fractal-like Viscek graphs, and the torus. This is joint work with Ravi Montenegro and Prasad Tetali.