zbMATH — the first resource for mathematics

Tight inequalities among set hitting times in Markov chains. (English) Zbl 1300.60083
Summary: Given an irreducible discrete time Markov chain on a finite state space, we consider the largest expected hitting time \( T(\alpha )\) of a set of stationary measure at least \( \alpha \) for \( \alpha \in (0,1)\). We obtain tight inequalities among the values of \( T(\alpha )\) for different choices of \( \alpha \). One consequence is that \( T(\alpha ) \leq T(1/2)/\alpha \) for all \( \alpha < 1/2\). As a corollary, we have that, if the chain is lazy in a certain sense as well as reversible, then \( T(1/2)\) is equivalent to the chain’s mixing time, answering a question of Y. Peres [Personal communication, 2012]. We furthermore demonstrate that the inequalities we establish give an almost everywhere pointwise limiting characterisation of possible hitting time functions \( T(\alpha )\) over the domain \( \alpha \in (0,1/2]\).

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
Full Text: DOI arXiv
[1] David J. Aldous, Some inequalities for reversible Markov chains, J. London Math. Soc. (2) 25 (1982), no. 3, 564 – 576. · Zbl 0489.60077
[2] David Aldous, László Lovász, and Peter Winkler, Mixing times for uniformly ergodic Markov chains, Stochastic Process. Appl. 71 (1997), no. 2, 165 – 185. · Zbl 0941.60080
[3] Graham Brightwell and Peter Winkler, Maximum hitting time for random walks on graphs, Random Structures Algorithms 1 (1990), no. 3, 263 – 276. · Zbl 0744.05044
[4] Navin Goyal, Problems from the AIM Workshop on Algorithmic Convex Geometry, accessed 11 February 2012: http://www.aimath.org/WWN/convexgeometry/convexgeometry.pdf, 2007.
[5] David A. Levin, Yuval Peres, and Elizabeth L. Wilmer, Markov chains and mixing times, American Mathematical Society, Providence, RI, 2009. With a chapter by James G. Propp and David B. Wilson. · Zbl 1160.60001
[6] L. Lovász, Random walks on graphs: a survey, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993) Bolyai Soc. Math. Stud., vol. 2, János Bolyai Math. Soc., Budapest, 1996, pp. 353 – 397. · Zbl 0854.60071
[7] Roberto Imbuzeiro Oliveira, Mixing and hitting times for finite Markov chains, Electron. J. Probab. 17 (2012), no. 70, 12. · Zbl 1251.60059
[8] Yuval Peres, personal communication, 2012.
[9] Yuval Peres and Perla Sousi, Mixing times are hitting times of large sets, electronically published in 2013, DOI 10.1007/s10959-013-0497-9. · Zbl 1323.60094
[10] -, personal communication, 2012.
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.