An Algorithmic Approach for Optimal Stopping of Random Walks and Its Extensions: With Appendix on Implementation for American Option Pricing

This booklet presents a new algorithm for solving an optimal stopping problem of random walks. It is based upon a novel use of the Fourier-Motzkin Elimination method (FME) and its computational complexity is demonstrated to be of O(n^2 ) where n represents the number of states the random walk can take. While the finite state Markov Decision Processes (MDPs) to which the optimal stopping problem of a random walk belongs are known to be solved in polynomial time by some algorithmic methods, the author believes the new algorithm has some technical merit in terms of its computational efficiency and its ease in implementation. As a random walk converges to a Brownian motion in some probabilistic sense, it is natural to view the optimal stopping of a Brownian motion likewise as a limit of an optimal stopping of a random walk. This booklet also provides for a proof of the convergence of the optimal value function of a random walk to presumably that of the continuous counterpart. The discussion in the main part is purely algorithmic and does not presuppose any applications or implementations in specific fields.
The Brownian motion and the random walk are arguably most deeply analyzed of all stochastic processes. As it is also widely adopted in a multitude of applications, it is this author’s hope that the present algorithm will be utilized when numerical solutions for the optimal stopping of these processes are needed in the respective fields of practice in natural sciences (biomedical and physical alike) and decision sciences including operations research and quantitative finance. In an appendix, as such example, some modeling and implementation issues of the proposed algorithm are addressed in the context of American option pricing that has been for years so prevalent in the area of quantitative finance.