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

Abstract

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.

Keywords:

• Markov chain
• optimal stopping
• elimination algorithm

AMS Subject Classification::

• primary 60J22, 62L15
• secondary 65C40, 90C40

Acknowledgements

The author would like to thank V.I. Arkin and A.D. Slastnikov for useful discussions, and I.M. Sonin, Yu.M. Kabanov, two referees, and AE for their very valuable remarks and suggestions. This work was partly supported by RFBR grant no. 10-01-00767-a.