Computational results for a stopping rule problem on averages
George L. Nemhauser, Donald A. Pierce · Naval Research Logistics Quarterly · 1968
Abstract Suppose x1, x2, … are independently distributed random variables with Pr (xi = 1) = Pr(xi = −1) = 1/2, and let sn = magnified image xi. The random variables are observed sequentially and after n observations, n = 1, 2, …, we can either stop and receive a return of sn/n or observe another random variable. Chow and Robbins [3] have shown that there exists a stopping rule that maximizes the expected return over all rules for which the probability of stopping is one. The optimum policy is characterized by a sequence of non‐decreasing integers kn, such that sn ≥ kn implies a stop. Calculations based upon lower bounds on kn developed by Chow and Robbins and upper bounds developed herein yield a substantial part of the optimal policy.