Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 288 - Probability

Sharad Goel

Stanford University

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 work is joint with Ravi Montenegro and Prasad Tetali.

Host: Jason Schweinsberg

October 20, 2005

10:00 AM

AP&M 6218

****************************