Efficient stopping rules for Markov chains
László Lovász, Peter M. Winkler · 1995
Let lf be the transition matrix, and a the initial state distribution.for a discrete-time finite-state irreducible Markov chain.A stopping rule for M is an algorithm which observes the progress of the chain and then stops it at some random time r; the distribution of the final state is denoted by ar.We give a useful characterization for stopping rules which are optimal for given target distribution r, in the sense that Some of the work described herein is joint with David Aldous.