Robbins' problem

In probability theory, Robbins' problem of optimal stopping, named after Herbert Robbins, is sometimes referred to as the fourth secretary problem or the problem of minimizing the expected rank with full information. Let

X

1

,

⋯

,

X

n

{\displaystyle X_{1},\cdots ,X_{n}}

be independent, identically distributed random variables, uniform on

[

0

,

1

]

{\displaystyle [0,1]}

. We observe the

X

k

{\displaystyle X_{k}}

's sequentially and must stop on exactly one of them. No recall of preceding observations is permitted. What stopping rule minimizes the expected rank of the selected observation, and what is its corresponding value?The general solution to this full-information expected rank problem is unknown. The major difficulty is that the problem is fully history-dependent, that is, the optimal rule depends at every stage on all preceding values, and not only on simpler sufficient statistics of these. Only bounds are known for the limiting value v as n goes to infinity, namely

1.908

<

v

<

2.329

{\displaystyle 1.908<v<2.329}

. These bounds are obtained by studying so-called memoryless strategies, that is strategies in which the decision to stop on

X

k

{\displaystyle X_{k}}

depends only on the value of

X

k

{\displaystyle X_{k}}

and not on the history of observations

X

1

,

⋯

,

X

k

−

1

{\displaystyle X_{1},\cdots ,X_{k-1}}

. It is known that there is some room to improve the lower bound by further computations for a truncated version of the problem within the class of memoryless stategeies. It is still not known how to improve on the upper bound for the limiting value, and this for whatever strategy.