We develop bounds for the second largest eigenvalue and spectral gap of a reversible Markov chain. The bounds depend on geometric quantities such as the maximum degree, diameter and covering number of associated graphs. The bounds compare well with exact answers for a variety of simple chains and seem better than bounds derived through Cheeger-like inequalities. They offer improved rates of convergence for the random walk associated to approximate computation of the permanent.
No takes yet. Share an insight, caveat, or question.
Diaconis et al. (1991) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: