Exact Mixing in an Unknown Markov Chain

Abstract

We give a simple stopping rule which will stop an unknown, irreducible $n$-state Markov chain at a state whose probability distribution is exactly the stationary distribution of the chain. The expected stopping time of the rule is bounded by a polynomial in the maximum mean hitting time of the chain. Our stopping rule can be made deterministic unless the chain itself has no random transitions.