Robbins problem

Article summary

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.…

Key claims

No claims recorded.

Discussion questions

1. Summarise the article in your own words. Which single claim would you verify first, and why?
2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.