A new approach to the solution of optimal stopping problem in a discrete time.

An optimal stopping problem of Markov chain with infinite horizon is considered. For the case of finite number m of states, Sonin proposed an algorithm, which allows to find the value function and the stopping set in not more than steps. The algorithm is based on a modification of Markov chain on each step, related with the elimination of the states which certainly belong to the continuation set. To solve the problem with arbitrary state space and to have a possibility of generalization to the continuous time, one needs to modify the procedure. We propose a procedure which is based on a sequential modification of the pay-off function for the same chain in such a way, that the value function is the same for both problems and the modified pay-off function is greater than the initial one on some set and is equal to it on the complement. We show the efficiency of this procedure. [ABSTRACT FROM AUTHOR]