World Library  
Flag as Inappropriate
Email this Article

Robbins' problem

Article Id: WHEBN0018617781
Reproduction Date:

Title: Robbins' problem  
Author: World Heritage Encyclopedia
Language: English
Subject: Mathematical optimization
Collection: Mathematical Optimization
Publisher: World Heritage Encyclopedia

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. Its statement is as follows.

Let X1, ... , Xn be independent, identically distributed random variables, uniform on [0, 1]. We observe the Xk'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. It is known that there is some room to improve the lower bound by further computations for a truncated version of the problem. It is still not known how to improve on the upper bound which stems from the subclass of memoryless threshold rules.


One of the motivations to study Robbins' Problem is that with its solution all classical (four) secretary problems would be solved. But the major reason is to understand how to cope with full history dependence in a (deceptively easy-looking) problem. On the Ester's Book International Conference in Israel (2006) Robbins' Problem was accordingly named one of the four most important problems in the field of optimal stopping and sequential analysis.


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.


  • "Minimizing the expected rank with full information", F. Thomas Bruss and Thomas S. Ferguson, Journal of Applied Probability 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 Statistics 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 Cat.Inist
  • "What is known about Robbins' Problem?" F. Thomas Bruss, Journal of Applied Probability Volume 42, #1 (2005), pp. 108–120 Euclid
  • "A continuous-time approach to Robbins' problem of minimizing the expected rank", F. Thomas Bruss and Yves Caoimhin Swan, Journal of Applied Probability Volume 46 #1, 1–18, (2009).
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.