Two Choice Optimal Stopping

David Assaf, Larry Goldstein & Ester Samuel-Cahn

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 V2n 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 V2n for a large class of F’s belonging to the domain of attraction (for the minimum) D(Gα), where Gα(x) = [1 − exp(−xα)] I(x≥0). The results are compared with those for the asymptotic behavior of the classical one choice value sequence V1n ,as well as with the “prophet value” sequence E(min{Xn, . . . ,X1}).

December, 2002
Published in: 
Advances of Applied Probability 36 (2004), 1116-1147