Two choice optimal stopping

Abstract

Let $X_n,...,X_1$ 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_n^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_n^2$ for a large class of $F$'s belonging to the domain of attraction (for the minimum) ${\cal D}(G^α)$, where $G^α(x)=[1-\exp(-x^α)]{\bf I}(x \ge 0)$. The results are compared with those for the asymptotic behavior of the classical one choice value sequence $V_n^1$, as well as with the ``prophet value" sequence $V_n^p=E(\min\{X_n,...,X_1\})$.

33 pages