On Successive Approximation Methods for Stochastic Problems: Probabilistic Interpretation, Ordering Heuristics, and Parallel Processing.

Simple probabilistic interpretations of classical numerical methods for solving optimal stopping problems are presented. In typical queueing theory and probabilistic modeling application the rate of convergence of the computation can be significantly improved by carefully ordering the sequence of updates performed in the course of the computation. Our probabilistic interpretation leads to simple heuristic to compute an ordering that thickens convergence. Simple efficient asynchronous parallel methods are presented, which retain the benefit of a good ordering while speeding up convergence by a factor of P if P processors participate. The ordering heuristic and parallel methods apply equally well to the problem of computing the invariant measure of a Markov chain.