Exact mixing in an unknown Markov chain. (English) Zbl 0823.60057

Electron. J. Comb. 2, Research paper R15, 12 p. (1995); printed version J. Comb. 2, 251-262 (1995).
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.
Reviewer: L.Laszlo


60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
Full Text: EuDML EMIS