Two Choice Optimal Stopping

Let Xn, . . . ,X1 be i.i.d. random variables with distribution function F. 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 stop at a value of X as small as possible. Let V^2 equal the expectation of the smaller of the two values chosen by the statistician when proceeding optimally. We obtain the asymptotic behavior of the sequence V^2 for a large class of F’s belonging to the domain of attraction (for the minimum) D(G^a), where G^a(x) = [1 - exp(-x^a)]I(x >= 0). The results are compared with those for the asymptotic behavior of the classical one choice value sequence V^1, as well as with the “prophet value” sequence E(min{Xn, . . . ,X1}).