Mixing and hitting times for finite Markov chains

Abstract

Let 0<α<1/2. We show that the mixing time of a continuous-time reversible Markov chain on a finite state space is about as large as the largest expected hitting time of a subset of stationary measure at least αof the state space. Suitably modified results hold in discrete time and/or without the reversibility assumption. The key technical tool is a construction of a random set A such that the hitting time of A is both light-tailed and a stationary time for the chain. We note that essentially the same results were obtained independently by Peres and Sousi [arXiv:1108.0133].

v2 has 18 pages. In revision for EJP

Cited by in corpus (9)

• Characterization of cutoff for reversible Markov chains
• Tight inequalities among set hitting times in Markov chains
• Mixing times are hitting times of large sets
• Mixing time bounds via bottleneck sequences
• Multiple Random Walks on Graphs: Mixing Few to Cover Many
• Missing Mass Concentration for Markov Chains
• Mixing times and moving targets
• Gradual convergence for Langevin dynamics on a degenerate potential
• Hitting time and mixing time bounds of Stein's factors