### Mixing and hitting times for finite Markov chains

**Roberto Imbuzeiro Oliveira**

*(IMPA)*

#### Abstract

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

#### References

- 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.

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