printable pdf
比利时vs摩洛哥足彩 ,
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

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