Exact mixing in an unknown Markov chain (Q1897681)

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.