Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T22:26:23.794Z Has data issue: false hasContentIssue false
  • English
  • Français

Mixing Times and Moving Targets

Published online by Cambridge University Press:  14 November 2013

PERLA SOUSI  and
PETER WINKLER
PERLA SOUSI
Affiliation:
DPMMS, University of Cambridge, Cambridge, UK (e-mail: p.sousi@statslab.cam.ac.uk)
PETER WINKLER
Affiliation:
Department of Mathematics, Dartmouth College, Hanover, NH 03755-3551, USA (e-mail: peter.winkler@dartmouth.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We consider irreducible Markov chains on a finite state space. We show that the mixing time of any such chain is equivalent to the maximum, over initial states x and moving large sets (As)s, of the hitting time of (As)s starting from x. We prove that in the case of the d-dimensional torus the maximum hitting time of moving targets is equal to the maximum hitting time of stationary targets. Nevertheless, we construct a transitive graph where these two quantities are not equal, resolving an open question of Aldous and Fill on a ‘cat and mouse’ game.

Keywords

Primary 60J10Secondary 60J2760G40

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 3 , May 2014 , pp. 460 - 476
Copyright
Copyright © Cambridge University Press 2013 

References

[1]Aldous, D. and Fill, J. Reversible Markov chains and random walks on graphs. In preparation. http://www.stat.berkeley.edu/~aldous/RWG/book.htmlGoogle Scholar
[2]Burchard, A. and Schmuckenschläger, M. (2001) Comparison theorems for exit times. Geom. Funct. Anal. 11 651–692.Google Scholar
[3]Griffiths, S., Kang, R. J., Oliveira, R. I. and Patel, V. (2012) Tight inequalities among set hitting times in Markov chains. ArXiv e-prints.Google Scholar
[4]Oliveira, R. I. (2011) Mixing and hitting times for finite Markov chains. Electron. J. Probab. 17, no. 70, 1–12.Google Scholar
[5]Levin, D. A., Peres, Y. and Wilmer, E. L. (2009) Markov Chains and Mixing Times, AMS.Google Scholar
[6]Lyons, R. and OveisGharan, S. Gharan, S. (2012) Sharp bounds on random walk eigenvalues via spectral embedding. ArXiv e-prints.Google Scholar
[7]Oliveira, R. I. (2012) On the coalescence time of reversible random walks. Trans. Amer. Math. Soc. 364 2109–2128.Google Scholar
[8]Peres, Y. and Sousi, P. Mixing times are hitting times of large sets. J. Theoret. Probab., to appear.Google Scholar
[9]Peres, Y. and Sousi, P. (2012) An isoperimetric inequality for the Wiener sausage. Geom. Funct. Anal. 22 1000–1014.Google Scholar