zbMATH — the first resource for mathematics

Mixing time bounds via the spectral profile. (English) Zbl 1109.60061
Summary: On complete, noncompact 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 \(L^\infty\) 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 \(\mathbb Z_a\times \mathbb Z_b\), to obtain tight bounds on the corresponding mixing times.

60J27 Continuous-time Markov processes on discrete state spaces
68Q99 Theory of computing
Full Text: DOI EuDML arXiv