zbMATH — the first resource for mathematics

Mixing and hitting times for finite Markov chains. (English) Zbl 1251.60059
Summary: Let \(0<\alpha<1/2\). We show that the mixing time of a continuous-time Markov chain on a finite state space is about as large as the largest expected hitting time of a subset of the state space with stationary measure \(\geq \alpha\). Suitably modified results hold in discrete time and/or without the reversibility assumption. The key technical tool in the proof is the construction of a random set \(A\) such that the hitting time of \(A\) is a light-tailed stationary time for the chain. We note that essentially the same results were obtained independently by Y. Peres and P. Sousi [“Mixing times are hitting times of large sets”, arXiv:1108.0133].

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
Full Text: DOI arXiv