Half-prophets and Robbins' Problem of Minimizing the Expected
Rank
F. THOMAS BRUSS and THOMAS S. FERGUSON
Abstract:
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.