Electronic Journal of Probability · 2006 · 74 citations · 13 references
Natural SciencesMathematicsPhysicsDynamical SystemsStochastic ProcessesThermodynamicsErgodic TheoryGraph TheoryMarkov ChainsMarkov ProcessesConductanceConductance-based ModelsConvergenceFinite Markov ChainsFinite-state Markov ChainsLower BoundsMarkov Chain Mixing RatesMixing Times
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 $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 $Z_a \times Z_b$, to obtain tight bounds on the corresponding mixing times.
13
Logarithmic Sobolev Inequalities
Leonard Gross · American Journal of Mathematics · 1975 · 1.8K citations