Robbins' problem (of optimal stopping)

Robbins' problem (of optimal stopping) is a problem of optimal stopping, sometimes referred to as the fourth secretary problem or the problem of minimizing the expected rank with full information. Its statement is as follows.

Let $X\_1,\; ...\; ,\; X\_n$ be independent, identically distributed random variables, uniform on $[0,1]$. We observe the $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, and only some bounds are known for the limiting value as $n$ goes to infinity.

History

Herbert Robbins presented the above described problem at the International Conference on Search and Selection in Real Time in Amherst, 1990. He concluded his address with the words "I should like to see this problem solved before I die". Scientists working in the field of optimal stopping have since called this problem "Robbins' Problem".

References

* Minimizing the expected rank with full information, F. T. Bruss and T. S. Ferguson, "J. Appl. Probab." "Volume" 30, #1 (1993), pp. 616-626
* Half-Prophets and Robbins' Problem of Minimizing the expected rank, F. T. Bruss and T. S. Ferguson, "Springer Lecture Notes in Stat." "Volume" 1 in honor of J.M. Gani, (1996), pp. 1-17
* The secretary problem; minimizing the expected rank with i.i.d. random variables, D. Assaf and E. Samuel-Cahn, "Adv. Appl. Prob." "Volume" 28, (1996), pp. 828-852 [http://cat.inist.fr/?aModele=afficheN&cpsidt=3259597 Cat.Inist]
* What is known about Robbins' Problem? F. T. Bruss, "J. Appl. Probab." "Volume" 42, #1 (2005), pp. 108-120 [http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.jap/1110381374 Euclid]