Return to Colloquia & Seminar listing
Evolving sets and mixing
ProbabilitySpeaker: | 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.