Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Evolving sets and mixing

Probability

Speaker: Dr. Ben Morris, UC Berkeley, Statistics Department
Location: 493 Kerr
Start time: Thu, Oct 31 2002, 3:10PM

We introduce a probabilistic technique that yields the sharpest bounds obtained on mixing times for Markov chains in terms of isoperimetric properties of the state space. We show that the bounds for mixing time in total variation obtained by Lovasz and Kannan can be refined to apply to the maximum relative deviation |p^n (x,y) / pi(y) -1| of the distribution at time n from the stationary distribution pi.