Robbins problem
≈ 2 min read
Names in other languages
- afRobbins problem
- anRobbins problem
- astRobbins problem
- DeutschRobbins problem
- EnglishRobbins problem
- EspañolRobbins problem
- FrançaisRobbins problem
- ItalianoRobbins problem
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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, \cdots , 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. 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 . These bounds are obtained by studying so-called memoryless strategies, that is strategies in which the decision to stop on X_k depends only on the value of X_k and not on the history of observations 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.…
The Robbins problem may mean either of: the Robbins conjecture that all Robbins algebras are Boolean algebras. Robbins' problem of optimal stopping in probability theory.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1364061812 under CC BY-SA 4.0; modifications have been made.