Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-26T19:35:59.810Z Has data issue: false hasContentIssue false
  • English
  • Français

What is Known About Robbins' Problem?

Part of: Stochastic processes

Published online by Cambridge University Press:  14 July 2016

F. Thomas Bruss
F. Thomas Bruss*
Affiliation:
Université Libre de Bruxelles
*
∗Postal address: Département de Mathématique, Université Libre de Bruxelles, CP 210, B-1050 Brussels, Belgium. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let X1, X2,…, Xn be independent, identically distributed random variables, uniform on [0,1]. We observe the Xk sequentially and must stop on exactly one of them. No recollection of the preceding observations is permitted. What stopping rule τ minimizes the expected rank of the selected observation? This full-information expected-rank problem is known as Robbins' problem. The general solution is still unknown, and only some bounds are known for the limiting value as n tends to infinity. After a short discussion of the history and background of this problem, we summarize what is known. We then try to present, in an easily accessible form, what the author believes should be seen as the essence of the more difficult remaining questions. The aim of this article is to evoke interest in this problem and so, simply by viewing it from what are possibly new angles, to increase the probability that a reader may see what seems to evade probabilistic intuition.

Keywords

Full informationoptimal selectionsecretary problemhalf-prophetmemoryless rulehistory dependencetruncationembeddingintegral-differential equation

MSC classification

Secondary: 60G40: Stopping times; optimal stopping problems; gambling theory
Type
Research Papers
Information
Journal of Applied Probability , Volume 42 , Issue 1 , March 2005 , pp. 108 - 120
Copyright
© Applied Probability Trust 2005 

References

Assaf, D. and Samuel-Cahn, E. (1996). The secretary problem: minimizing the expected rank with i.i.d. random variables. Adv. Appl. Prob. 28, 828–852.Google Scholar
Brennan, M. D. and Durrett, R. (1987). Splitting intervals. II. Limit laws for lengths. Prob. Theory and Relat. Fields 75, 109–127.Google Scholar
Bruss, F. T. (2000). Sum the odds to one and stop. Ann. Prob. 28, 1384–1391.Google Scholar
Bruss, F. T. and Delbaen, F. (2001). Optimal rules for the sequential selection of monotone subsequences of maximum expected length. Stoch. Process. Appl. 96, 313–342.Google Scholar
Bruss, F. T. and Ferguson, T. S. (1993). Minimizing the expected rank with full information. J. Appl. Prob. 30, 616–626.Google Scholar
Bruss, F. T. and Ferguson, T. S. (1996). Half-prophets and Robbins' problem of minimizing the expected rank. In Athens Conf. Appl. Prob. Time Ser. Anal. (Lecture Notes Statist. 114), Vol. 1, Springer, New York, pp. 1–17.Google Scholar
Chow, Y. S., Moriguti, S., Robbins, H. and Samuels, S. M. (1964). Optimal selection based on relative ranks. Israel J. Math. 2, 81–90.Google Scholar
Dynkin, E. B. and Juschkewitsch, A. A. (1969). Sätze und Aufgaben über Markoffsche Prozesse. Springer, Berlin.Google Scholar
Ferguson, T. S. (1989a). Who solved the secretary problem? Statist. Sci. 4, 282–289.Google Scholar
Ferguson, T. S. (1989b). [Who solved the secretary problem?]: rejoinder. Statist. Sci. 4, 294–296.Google Scholar
Gardner, M. (1960). Mathematical games. Scientific Amer. 3, 202–203.Google Scholar
Gilbert, J. P. and Mosteller, F. (1966). Recognizing the maximum of a sequence. J. Amer. Statist. Assoc. 61, 35–73.Google Scholar
Gnedin, A. V. (2003). Best choice from the planar Poisson process. Stoch. Process. Appl. 111, 317–354.Google Scholar
Hubert, S. L. and Pyke, R. (1997). A particular application of Brownian motion to sequential analysis. Statistica Sinica 7, 109–127.Google Scholar
Kakutani, S. (1976). A problem of equidistribution on the unit interval [0, 1]. In Measure Theory (Proc. Conf. Oberwolfach, June 1975; Lecture Notes Math. 451), eds Bellow, A. and Kolzow, D., Springer, Berlin, pp. 369–376.Google Scholar
Kennedy, D. P. and Kertz, R. P. (1990). Limit theorems for threshold-stopped random variables with applications to optimal stopping. Adv. Appl. Prob. 22, 396–411.Google Scholar
Lai, T. L. and Siegmund, D. (1986). The contributions of Herbert Robbins to mathematical statistics. Statist. Sci. 1, 276–284.CrossRefGoogle Scholar
Lindley, D. (1961). Dynamic programming and decision theory. Appl. Statist. 10, 39–51.Google Scholar
Monro, S. and Robbins, H. (1951). A stochastic approximation method. Ann. Math. Statist. 22, 400–407.Google Scholar
Moser, L. (1956). On a problem of Cayley. Scripta Math. 22, 289–292.Google Scholar
Presman, E. and Sonin, I. (1972). The best choice problem for a random number of objects. Theory Prob. Appl. 17, 657–668.CrossRefGoogle Scholar
Pyke, R. and van Zwet, W. R. (2004). Weak convergence results for the Kakutani interval splitting procedure. Ann. Prob. 32, 380–423.Google Scholar
Robbins, H. (1989). [Who solved the secretary problem?]: comment. Statist. Sci. 4, 291.CrossRefGoogle Scholar
Robbins, H. (1991). Remarks on the secretary problem. Amer. J. Math. Manag. Sci. 11, 25–37.Google Scholar
Samuels, S. M. (1991). Secretary problems. In Handbook of Sequential Analysis (Statist. Textbooks Monogr. 118), eds Gosh, B. K. and Sen, P. K., Marcel Dekker, New York, pp. 381–405.Google Scholar
Siegmund, D. (2003a). Herbert Robbins and sequential analysis. Ann. Statist. 31, 349–365.Google Scholar
Siegmund, D. (2003b). The publications and writings of Herbert Robbins. Ann. Statist. 31, 407–413.Google Scholar
Vanderbei, R. J. (1980). The optimal choice of a subset of a population. Math. Operat. Res. 5, 481–486.Google Scholar