Faster mixing by isoperimetric inequalities

This thesis is concerned with isoperimetric methods for studying the rate at which Markov chains approach their steady state distribution. We begin by proving a new isoperimetric bound on the mixing time using a quantity which we call blocking conductance φ(x), this is an extension of conductance Φ and average conductance Φ(x). We then look at the three methods for bounding conductance of which we are aware: geometry, induction, and canonical paths. We extend all three of these methods and obtain bounds on the blocking conductance φ(x) or the conductance function Φ(x); in all three cases these give significant improvements over conductance based bounds for the mixing time. We end by considering a new isoperimetric quantity h+2 (x); we prove a mixing time bound in terms of h 2 (x) and conjecture a stronger theorem which may give optimal mixing time bounds for a wide range of Markov chains including geometric, inductive, and product Markov chains