\magnification=1440
\font\bigtenrm=cmr10 scaled\magstep4

Abstract for 
Laszlo Lovasz and Peter Winkler, Exact Mixing in an Unknown Markov Chain   

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.


\bye