Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

Request Permissions   Purchase Content 
 
 

 

Tight inequalities among set hitting times in Markov chains


Authors: Simon Griffiths, Ross J. Kang, Roberto Imbuzeiro Oliveira and Viresh Patel
Journal: Proc. Amer. Math. Soc. 142 (2014), 3285-3298
MSC (2010): Primary 60J10
DOI: https://doi.org/10.1090/S0002-9939-2014-12045-4
Published electronically: May 21, 2014
MathSciNet review: 3223383
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] David J. Aldous, Some inequalities for reversible Markov chains, J. London Math. Soc. (2) 25 (1982), no. 3, 564-576. MR 657512 (83f:60098), https://doi.org/10.1112/jlms/s2-25.3.564
  • [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. MR 1484158 (98i:60062), https://doi.org/10.1016/S0304-4149(97)00037-9
  • [3] Graham Brightwell and Peter Winkler, Maximum hitting time for random walks on graphs, Random Structures Algorithms 1 (1990), no. 3, 263-276. MR 1099792 (92e:60134), https://doi.org/10.1002/rsa.3240010303
  • [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, with a chapter by James G. Propp and David B. Wilson, American Mathematical Society, Providence, RI, 2009. MR 2466937 (2010c:60209)
  • [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. MR 1395866 (97a:60097)
  • [7] Roberto Imbuzeiro Oliveira, Mixing and hitting times for finite Markov chains, Electron. J. Probab. 17 (2012), no. 70, 12. MR 2968677, https://doi.org/10.1214/EJP.v17-2274
  • [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.
  • [10] -, personal communication, 2012.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 60J10

Retrieve articles in all journals with MSC (2010): 60J10


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

DOI: https://doi.org/10.1090/S0002-9939-2014-12045-4
Keywords: Markov chains, hitting times.
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
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society