Half-prophets and Robbins' Problem of Minimizing the Expected Rank



Let X(1),X(2), . . ., X(n) be i.i.d. random variables with a known continuous distribution function. Robbins' problem is to find a stopping rule, T, adapted to this sequence, that minimizes E(R(T)), where R(1), . . ., R(n) are the absolute ranks of X(1), . . ., X(n). An upper bound (obtained by memoryless threshold rules) and a procedure to obtain lower bounds of the value are known, but the essence of the problem is still unsolved. The difficulty is that the optimal strategy depends for all n >2 in an intractable way on the whole history of preceding observations. The goal of this article is to understand better the structure of both optimal memoryless threshold rules and the (overall) optimal rule. We prove that the optimal rule is a "stepwise" monotone increasing threshold-function rule and then study its property of, what we call, full history-dependence. For each n, we describe a tractable statistic of preceding observations which is sufficient for optimal decisions of decision makers with half-prophetical abilities who can do generally better than we. It is shown that their advice can always be used to improve strictly on memoryless rules, and we determine such an improved rule for all sufficiently large n. We do not know how to construct asymptotically relevant improvements.