Mixing Times and Moving Targets

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