zbMATH — the first resource for mathematics

Mixing times are hitting times of large sets. (English) Zbl 1323.60094
Summary: We consider irreducible reversible discrete time Markov chains on a finite state space. Mixing times and hitting times are fundamental parameters of the chain. We relate them by showing that the mixing time of the lazy chain is equivalent to the maximum over initial states \(x\) and large sets \(A\) of the hitting time of \(A\) starting from \(x\). We also prove that the first time when averaging over two consecutive time steps is close to stationarity is equivalent to the mixing time of the lazy version of the chain.

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60G40 Stopping times; optimal stopping problems; gambling theory
Full Text: DOI arXiv
[1] Aldous, D., Fill, J.: Reversible Markov chains and random walks on graphs. In preparation, http://www.stat.berkeley.edu/aldous/RWG/book.html
[2] Aldous, DJ, Some inequalities for reversible Markov chains, J. Lond. Math. Soc. (2), 25, 564-576, (1982) · Zbl 0489.60077
[3] Baxter, JR; Chacon, RV, Stopping times for recurrent Markov processes, Ill. J. Math., 20, 467-475, (1976) · Zbl 0335.60036
[4] Ding, J., Peres, Y.: Sensitivity of mixing times, 2013. arXiv:1304.0244 · Zbl 1307.60051
[5] Griffiths, S., Kang, R.J., Imbuzeiro Oliveira, R., Patel, V.: Tight inequalities among set hitting times in Markov chains, 2012. to appear. In Proceedings AMS · Zbl 1300.60083
[6] Imbuzeiro Oliveira, R.. Mixing and hitting times for finite Markov chains. Electron. J. Probab., 17(70), 12 (2012) · Zbl 1251.60059
[7] Levin, D.A., Peres, Y., Wilmer, E.L.: Markov chains and mixing times. American Mathematical Society, Providence, RI, : With a chapter by Propp, J.G., Wilson, D.B. (2009) · Zbl 1160.60001
[8] Lovász, L., Winkler, P.: Efficient stopping rules for markov chains. In: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’95, pp. 76-82, New York, NY, USA, 1995. ACM · Zbl 0921.60062
[9] Lovász, L., Winkler, P.: Mixing times. In: Microsurveys in Discrete Probability (Princeton, NJ, 1997), volume 41 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pp. 85-133. Am. Math. Soc., Providence, RI, 1998 · Zbl 0908.60065
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.