probability theory Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set o ...

, Robbins' problem of

optimal stopping In mathematics, the theory of optimal stopping or early stopping : (For French translation, secover storyin the July issue of ''Pour la Science'' (2009).) is concerned with the problem of choosing a time to take a particular action, in order to ...

, named after

Herbert Robbins Herbert Ellis Robbins (January 12, 1915 – February 12, 2001) was an American mathematician and statistician. He did research in topology, measure theory, statistics, and a variety of other fields. He was the co-author, with Richard Courant ...

, is sometimes referred to as the fourth

secretary problem The secretary problem demonstrates a scenario involving optimal stopping theory For French translation, secover storyin the July issue of ''Pour la Science'' (2009). that is studied extensively in the fields of applied probability, statistics, an ...

or the problem of minimizing the expected rank with full information. Its statement is as follows. Let ''X''₁, ... , ''X''_''n'' be independent, identically distributed

random variable A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. It is a mapping or a function from possible outcomes (e.g., the po ...

uniform A uniform is a variety of clothing worn by members of an organization while participating in that organization's activity. Modern uniforms are most often worn by armed forces and paramilitary organizations such as police, emergency services, se ...

on , 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 < ''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)

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

and

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

History

presented the above described problem at the

International Conference on Search and Selection in Real Time International is an adjective (also used as a noun) meaning "between nations". International may also refer to: Music Albums * ''International'' (Kevin Michael album), 2011 * ''International'' (New Order album), 2002 * ''International'' (The T ...

Amherst Amherst may refer to: People * Amherst (surname), including a list of people with the name * Earl Amherst of Arracan in the East Indies, a title in the British Peerage; formerly ''Baron Amherst'' * Baron Amherst of Hackney of the City of London, ...

, 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

* {{cite journal, last1=Chow, first1=Y.S., last2=Moriguti, first2=S., last3=Robbins, first3=H., last4=Samuels, first4=S.M., title=Optimal Selection Based on Relative Rank, journal=

Israel Journal of Mathematics '' Israel Journal of Mathematics'' is a peer-reviewed mathematics journal published by the Hebrew University of Jerusalem (Magnes Press). Founded in 1963, as a continuation of the ''Bulletin of the Research Council of Israel'' (Section F), the jou ...

, year=1964, volume=2, issue=2, pages=81–90, doi=10.1007/bf02759948, doi-access=free * "Minimizing the expected rank with full information",

F. Thomas Bruss Franz Thomas Bruss is Emeritus Professor of Mathematics at the Université Libre de Bruxelles, where he had been director of "Mathématiques Générales" and co-director of the probability chair, and where he continues his research as invited profe ...

and

Thomas S. Ferguson Thomas Shelburne Ferguson (born December 14, 1929) is an American mathematician and statistician. He is a professor emeritus of mathematics and statistics at the University of California, Los Angeles. Education and career Ferguson was born in O ...

, ''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–85
Cat.Inist
* "What is known about Robbins' Problem?"

, ''Journal of Applied Probability'' ''Volume'' 42, #1 (2005), pp. 108–12
Euclid
* "A continuous-time approach to Robbins' problem of minimizing the expected rank",

and Yves Caoimhin Swan, ''Journal of Applied Probability'' ''Volume 46'' #1, 1–18, (2009). Stochastic optimization