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
****************************