The elimination algorithm for the problem of optimal stopping (Q1299925)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The elimination algorithm for the problem of optimal stopping |
scientific article |
Statements
The elimination algorithm for the problem of optimal stopping (English)
0 references
25 April 2000
0 references
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)].
0 references
optimal stopping
0 references
secretary problem
0 references
elimination algorithm
0 references
Markov chain
0 references
discrete time
0 references
sequential analysis discounting
0 references