Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

 

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
Published electronically: May 21, 2014
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?)


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: http://dx.doi.org/10.1090/S0002-9939-2014-12045-4
PII: S 0002-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.