Maximizing expected value with two stage stopping rules

David Assaf, Larry Goldstein and Ester Samuel-Cahn

Let Xn,…,X1 be i.i.d. random variables with distribution function F and finite expectation. A statistician, knowing F, observes the X values sequentially and is given two chances to choose X's using stopping rules. The statistician's goal is to select a value of X as large as possible. Let Vn2 equal the expectation of the larger of the two values chosen by the statistician when proceeding optimally. We obtain the asymptotic behavior of the sequence Vn2 for a large class of F's belonging to the domain of attraction (for the maximum) D(GIIα), where GIIα (x) = exp(-x-α)Ι(x > 0) with α > 1. The results are compared with those for the asymptotic behavior of the classical one choice value sequence Vn1, as well as with the ""prophet value"" sequence E(max{Xn,…,X1}), and indicate that substantial improvement is obtained when given two chances to stop, rather than one.

March, 2004
Published in: 
Random Walks, Sequential Analysis and Related Topics, Chao Agnes Hsiung, Zhiliang Ying and Cun-Hui Zhang, Eds. World Scientific, Singapore (2006), 3-27