Mixing and hitting times for finite Markov chains

Roberto Imbuzeiro Oliveira (IMPA)


Let $0<\alpha<1/2$. We show that 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 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 Peres and Sousi.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-12

Publication Date: August 27, 2012

DOI: 10.1214/EJP.v17-2274


  • List of open problems from AIM Workshop on Algorithmic Convex Geometry. http://www.aimath.org/WWN/convexgeometry/convexgeometry.pdf. Compiled by Navin Goyal (2009).
  • Aldous, David J. Some inequalities for reversible Markov chains. J. London Math. Soc. (2) 25 (1982), no. 3, 564--576. MR0657512
  • Aldous, D. and Fill, J.A.: Reversible Markov Chains and Random Walks on Graphs. Book draft available from http://www.stat.berkeley.edu/~aldous/.
  • Aldous, David; Lovász, László; Winkler, Peter. Mixing times for uniformly ergodic Markov chains. Stochastic Process. Appl. 71 (1997), no. 2, 165--185. MR1484158
  • Levin, David A.; Peres, Yuval; Wilmer, Elizabeth L. Markov chains and mixing times. With a chapter by James G. Propp and David B. Wilson. American Mathematical Society, Providence, RI, 2009. xviii+371 pp. ISBN: 978-0-8218-4739-8 MR2466937
  • Lovász, László; Winkler, Peter. Mixing of random walks and other diffusions on a graph. Surveys in combinatorics, 1995 (Stirling), 119--154, London Math. Soc. Lecture Note Ser., 218, Cambridge Univ. Press, Cambridge, 1995. MR1358634
  • Peres,Y.: Personal communication (2011).
  • Peres, Y. and Sousi, P.: Mixing times are hitting times of large sets, arXiv: 1108.0133.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.