Tight inequalities among set hitting times in Markov chains
HTML articles powered by AMS MathViewer
- by Simon Griffiths, Ross J. Kang, Roberto Imbuzeiro Oliveira and Viresh Patel PDF
- Proc. Amer. Math. Soc. 142 (2014), 3285-3298 Request permission
Abstract:
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 ) \le 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 Peres. 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]$.References
- David J. Aldous, Some inequalities for reversible Markov chains, J. London Math. Soc. (2) 25 (1982), no. 3, 564–576. MR 657512, DOI 10.1112/jlms/s2-25.3.564
- 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. MR 1484158, DOI 10.1016/S0304-4149(97)00037-9
- Graham Brightwell and Peter Winkler, Maximum hitting time for random walks on graphs, Random Structures Algorithms 1 (1990), no. 3, 263–276. MR 1099792, DOI 10.1002/rsa.3240010303
- Navin Goyal, Problems from the AIM Workshop on Algorithmic Convex Geometry, accessed 11 February 2012: http://www.aimath.org/WWN/convexgeometry/convexgeometry.pdf, 2007.
- 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. MR 2466937, DOI 10.1090/mbk/058
- 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. MR 1395866
- Roberto Imbuzeiro Oliveira, Mixing and hitting times for finite Markov chains, Electron. J. Probab. 17 (2012), no. 70, 12. MR 2968677, DOI 10.1214/EJP.v17-2274
- Yuval Peres, personal communication, 2012.
- Yuval Peres and Perla Sousi, Mixing times are hitting times of large sets, electronically published in 2013, DOI 10.1007/s10959-013-0497-9.
- —, personal communication, 2012.
Additional Information
- Simon Griffiths
- Affiliation: Instituto Nacional de Matemática Pura e Aplicada (IMPA), Rio de Janeiro, Brazil
- Address at time of publication: Department of Statistics, University of Oxford, Oxford, United Kingdom
- MR Author ID: 853857
- Email: simon.griffiths@stats.ox.ac.uk
- Ross J. Kang
- Affiliation: Centrum Wiskunde & Informatica, Amsterdam, Netherlands
- Address at time of publication: Department of Applied Stochastics, Radboud University Nijmegen, Nijmegen, Netherlands
- Email: ross.kang@gmail.com
- Roberto Imbuzeiro Oliveira
- Affiliation: Instituto Nacional de Matemática Pura e Aplicada (IMPA), Rio de Janeiro, Brazil
- Email: rimfo@impa.br
- Viresh Patel
- Affiliation: School of Mathematics, University of Birmingham, Birmingham, United Kingdom
- Address at time of publication: School of Mathematical Sciences, Queen Mary University of London, London, United Kingdom
- Email: viresh.s.patel@googlemail.com
- Received by editor(s): August 31, 2012
- Received by editor(s) in revised form: September 21, 2012
- Published electronically: May 21, 2014
- Additional Notes: The first author was supported by CNPq Proc. 500016/2010-2.
This work was begun while the second author was at Durham University, supported by EPSRC grant EP/G066604/1. He is currently supported by an NWO Veni grant.
The third author was supported by a Bolsa de Produtividade em Pesquisa and a Universal grant from CNPq, Brazil.
This work was begun while the fourth author was at Durham University, where he was supported by EPSRC grant EP/G066604/1. The work was concluded while the fourth author was at the University of Birmingham, where he was supported by EPSRC grant EP/J008087/1. - Communicated by: David Levin
- © Copyright 2014
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 142 (2014), 3285-3298
- MSC (2010): Primary 60J10
- DOI: https://doi.org/10.1090/S0002-9939-2014-12045-4
- MathSciNet review: 3223383