Robbins' problem (of optimal stopping)
Encyclopedia
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 variable
s, 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.
s 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
.
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.
Probability theory
Probability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...
, Robbins' problem of optimal stopping
Optimal stopping
In mathematics, the theory of optimal stopping is concerned with the problem of choosing a time to take a particular action, in order to maximise an expected reward or minimise an expected cost. Optimal stopping problems can be found in areas of statistics, economics, and mathematical finance...
, named after Herbert Robbins
Herbert Robbins
Herbert Ellis Robbins was an American mathematician and statistician who did research in topology, measure theory, statistics, and a variety of other fields. He was the co-author, with Richard Courant, of What is Mathematics?, a popularization that is still in print. The Robbins lemma, used in...
, is sometimes referred to as the fourth secretary problem
Secretary problem
The secretary problem is one of many names for a famous problem of theoptimal stopping theory.The problem has been studied extensively in the fields ofapplied probability, statistics, and decision theory...
or the problem of minimizing the expected
Expected value
In probability theory, the expected value of a random variable is the weighted average of all possible values that this random variable can take on...
rank with full information. Its statement is as follows.
Let X1, ... , Xn be independent, identically distributed random variable
Random variable
In probability and statistics, a random variable or stochastic variable is, roughly speaking, a variable whose value results from a measurement on some type of random process. Formally, it is a function from a probability space, typically to the real numbers, which is measurable functionmeasurable...
s, 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.
Importance
One of the motivations to study Robbins' Problem is that with its solution all classical (four) secretary problemSecretary problem
The secretary problem is one of many names for a famous problem of theoptimal stopping theory.The problem has been studied extensively in the fields ofapplied probability, statistics, and decision theory...
s 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
Optimal stopping
In mathematics, the theory of optimal stopping is concerned with the problem of choosing a time to take a particular action, in order to maximise an expected reward or minimise an expected cost. Optimal stopping problems can be found in areas of statistics, economics, and mathematical finance...
and sequential analysis
Sequential analysis
In statistics, sequential analysis or sequential hypothesis testing is statistical analysis where the sample size is not fixed in advance. Instead data are evaluated as they are collected, and further sampling is stopped in accordance with a pre-defined stopping rule as soon as significant results...
.
History
Herbert RobbinsHerbert Robbins
Herbert Ellis Robbins was an American mathematician and statistician who did research in topology, measure theory, statistics, and a variety of other fields. He was the co-author, with Richard Courant, of What is Mathematics?, a popularization that is still in print. The Robbins lemma, used in...
presented the above described problem at the International Conference on Search and Selection in Real Time in Amherst
Amherst, Massachusetts
Amherst is a town in Hampshire County, Massachusetts, United States in the Connecticut River valley. As of the 2010 census, the population was 37,819, making it the largest community in Hampshire County . The town is home to Amherst College, Hampshire College, and the University of Massachusetts...
, 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
Optimal stopping
In mathematics, the theory of optimal stopping is concerned with the problem of choosing a time to take a particular action, in order to maximise an expected reward or minimise an expected cost. Optimal stopping problems can be found in areas of statistics, economics, and mathematical finance...
have since called this problem Robbins' Problem.