Optimal Look-Ahead Stopping Rules for Simple Random Walk

In a stopping rule problem, a real-time player decides to stop or continue at stage n based on the observations up to that stage, but in a k-step look-ahead stopping rule problem, we suppose the player knows k steps ahead. The aim of this Ph.D. dissertation is to study this type of prophet problems for simple random walk, determine the optimal stopping rule and calculate the expected return for them. The optimal one-step look-ahead stopping rule for a finite simple random walk is determined in this work. We also study two infinite horizon stopping rule problems, sum with negative drift problems and discounted sum problems. The optimal one, two and three-step look-ahead stopping rules are introduced for the sum with negative drift problem for simple random walk. We also compare the maximum expected returns and calculate the upper bound for the advantage of the prophet over the decision maker. The last chapter of this dissertation concentrates on the discounted sum problem for simple random walk. Optimal one-step look-ahead stopping rule is defined and lastly we compare the optimal expected return for one-step look-ahead prophet with a real-time decision maker.