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

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