Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-14T15:54:46.216Z Has data issue: false hasContentIssue false
  • English
  • Français

The secretary problem of minimizing the expected rank: a simple suboptimal approach with generalizations

Part of:Sequential methodsLimit theoremsParametric inference

Published online by Cambridge University Press:  01 July 2016

Abba M. Krieger and
Ester Samuel-Cahn
Abba M. Krieger*
Affiliation:
University of Pennsylvania
Ester Samuel-Cahn*
Affiliation:
The Hebrew University of Jerusalem
*
∗ Postal address: Department of Statistics, The Wharton School University of Pennsylvania, Philadelphia, PA 19104-6340, USA. Email address: krieger@wharton.upenn.edu
∗∗ Postal address: Department of Statistics (and Center for Rationality), The Hebrew University of Jerusalem, Jerusalem, 91905, Israel. Email address: scahn@mscc.huji.ac.il
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.

The secretary problem for selecting one item so as to minimize its expected rank, based on observing the relative ranks only, is revisited. A simple suboptimal rule, which performs almost as well as the optimal rule, is given. The rule stops with the smallest i such that R i ≤ic/(n+1-i) for a given constant c, where R i is the relative rank of the ith observation and n is the total number of items. This rule has added flexibility. A curtailed version thereof can be used to select an item with a given probability P, P<1. The rule can be used to select two or more items. The problem of selecting a fixed percentage, α, 0<α<1, of n, is also treated. Numerical results are included to illustrate the findings.

Keywords

Secretary problemgroup selection rulessuboptimal rulenear optimal ruleabsolute rankrelative rank60F15

MSC classification

Primary:62L99: None of the above, but in this section
Secondary:62F07: Ranking and selection60F15: Strong theorems

Information

Type
General Applied Probability
Information
Advances in Applied Probability , Volume 41 , Issue 4 , December 2009, pp. 1041 - 1058
Copyright
Copyright © Applied Probability Trust 2009 

Footnotes

Supported by funds from the Marcy Bogen Chair of Statistics at the Hebrew University of Jerusalem.

Supported by the Israel Science Foundation Grant 467/04.

References

Barbour, A. D., Holst, L. and Janson, S. (1992). Poisson Approximation. Oxford University Press.CrossRefGoogle Scholar
Chow, Y. S., Moriguti, S., Robbins, H. and Samuels, S. M. (1964). Optimal selection based on relative rank (the ‘secretary problem’). Israel J. Math 2, 81–90.CrossRefGoogle Scholar
Feller, W. (1971). An Introduction to Probability Theory and Its Applications, Vol. 2, 2nd edn. John Wiley, New York.Google Scholar
Ferguson, T. S. (2002). Optimal Stopping and Applications. Available at http://www.math.ucla.edu/∼tom/stopping/contents.html.Google Scholar
Krieger, A. M., Pollak, M. and Samuel-Cahn, E. (2007). Select sets: rank and file. Ann. Appl. Prob. 17, 360–385.CrossRefGoogle Scholar
Robbins, H. and Siegmund, D. (1971). A convergence theorem for nonnegative almost supermartingales and some applications. In Optimizing Methods in Statistics, ed. Rustagi, J. S., Academic Press, New York, pp. 233–257.Google Scholar
Yeo, A. J. and Yeo, G. F. (1994). Selecting satisfactory secretaries. Austral. J. Statist. 36, 185–198.CrossRefGoogle Scholar