The elimination algorithm for the problem of optimal stopping (Q1299925)

The author presents a new method for solving the optimal stopping problem [cf. \textit{Y. S. Chow, H. Robbins} and \textit{D. Siegmund}, ``Great expectations: The theory of optimal stopping'' (1971; Zbl 0233.60044)] of Markov chains with countable state spaces. The algorithm is based on the idea of elimination of states where stopping is nonoptimal and the corresponding recomputation of transition probabilities. After a short review of the main existing algorithms (direct solution of the Bellman equation, value iteration, and linear programming), the elimination algorithm (Theorem 1) is proved, and three examples of its application are given, including solution of the classical secretary problem [cf. \textit{T. S. Ferguson}, Stat. Sci. 4, No. 3, 282-296 (1989; Zbl 0788.90080)].