We provide new upper bounds for mixing times of general finite Markov chains. We use these bounds to show that the total variation mixing time is robust under rough isometry for bounded degree graphs that are roughly isometric to trees.
Another variant on the Lov 'asz and Kannan result was obtained by Morris and Peres @cite_12 , who sharpened in several ways, including allowing non-reversible chains and bounding the larger @math -mixing time. This mantle was then taken up by Goel, Montenegro and Tet ali @cite_0 , who used the spectral profile @math instead of the conductance profile @math . For reversible chains @math may be thought of as the smallest eigenvalue of the Laplacian on the graph restricted to @math , minimized over all sets @math of invariant measure at most @math ; in fact the definition of @math used in @cite_0 is different, but for reversible chains it is equivalent to this definition up to constants provided that @math . Goel, Montenegro and Tet ali gave an upper bound involving @math , and were able to recover the result of Morris and Peres @cite_12 in the reversible case by using a discrete Cheeger inequality to relate @math to @math .
@cite_0 @cite_12
1996447604 2028920027
On complete, non-compact manifolds and infinite graphs, Faber-Krahn inequalities have been used to estimate the rate of decay of the heat kernel. We develop this technique in the setting of finite Markov chains, proving upper and lower @math mixing time bounds via the spectral profile. This approach lets us recover and refine previous conductance-based bounds of mixing time (including the Morris-Peres result), and in general leads to sharper estimates of convergence rates. We apply this method to several models including groups with moderate growth, the fractal-like Viscek graphs, and the product group @math , to obtain tight bounds on the corresponding mixing times. We show that a new probabilistic technique, recently introduced by the first author, yields the sharpest bounds obtained to date on mixing times of Markov chains in terms of isoperimetric properties of the state space (also known as conductance bounds or Cheeger inequalities). We prove 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) π(y)−1| of the distribution at time n from the stationary distribution π. We then extend our results to Markov chains on infinite state spaces and to continuous-time chains. Our approach yields a direct link between isoperimetric inequalities and heat kernel bounds; previously, this link rested on analytic estimates known as Nash inequalities.