| 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 &phis;(x), this is an extension of conductance phi and average conductance phi(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 &phis;(x) or the conductance function phi(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. |
