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 |
Description
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.