Efficient Stopping Rules for Markov Chains (Extended Abstract)

Let M be the transition matrix, and oe 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 \Gamma; the distribution of the final state is denoted by oe \Gamma . We give a useful characterization for stopping rules which are optimal for given target distribution ø , in the sense that oe \Gamma = ø and the expected stopping time E\Gamma is minimal. Four classes of optimal stopping rules are described, including a unique "threshold" rule which also minimizes max(\Gamma). The minimum value of E\Gamma, which we denote by H(oe;ø ), is easily computable from the hitting times of M . For applications in computing, the most important c..