Mixing times and moving targets

Abstract

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 $(A_s{)}_s$, of the hitting time of $(A_s{)}_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.

References in corpus (2)

• Mixing and hitting times for finite Markov chains
• Tight inequalities among set hitting times in Markov chains

Cited by in corpus (1)

• A permuted random walk exits faster