Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-25T07:29:23.115Z Has data issue: false hasContentIssue false
  • English
  • Français

The secretary problem: minimizing the expected rank with I.I.D. random variables

Part of: Stochastic processes

Published online by Cambridge University Press:  01 July 2016

David Assaf  and
Ester Samuel-Cahn
David Assaf*
Affiliation:
The Hebrew University of Jerusalem
Ester Samuel-Cahn*
Affiliation:
The Hebrew University of Jerusalem
*
∗ Postal address for both authors: Department of Statistics, The Hebrew University of Jerusalem, Jerusalem, 91905, Israel.
∗ Postal address for both authors: Department of Statistics, The Hebrew University of Jerusalem, Jerusalem, 91905, Israel.
Get access Rights & Permissions [Opens in a new window]

Abstract

n candidates, represented by n i.i.d. continuous random variables X1, …, Xn with known distribution arrive sequentially, and one of them must be chosen, using a non-anticipating stopping rule. The objective is to minimize the expected rank (among the ranks of X1, …, Xn) of the candidate chosen, where the best candidate, i.e. the one with smallest X-value, has rank one, etc. Let the value of the optimal rule be Vn, and lim Vn = V. We prove that V > 1.85. Limiting consideration to the class of threshold rules of the form tn = min {k: Xk ≦ ak for some constants ak, let Wn be the value of the expected rank for the optimal threshold rule, and lim Wn = W. We show 2.295 < W < 2.327.

Keywords

SECRETARY PROBLEMFULL INFORMATIONSTOPPING RULETHRESHOLD RULEFAILURE RATEINDIFFERENCE ON BOUNDARYCALCULUS OF VARIATIONS

MSC classification

Primary: 60G40: Stopping times; optimal stopping problems; gambling theory
Type
General Applied Probablity
Information
Advances in Applied Probability , Volume 28 , Issue 3 , September 1996 , pp. 828 - 852
Copyright
Copyright © Applied Probability Trust 1996 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

This article was awarded the Joseph Levy prize of the Operations Research Society of Israel, 1994.

References

Abramowitz, M. and Stegun, I. A. (1964) Handbook of Mathematical Functions. National Bureau of Standards, Washington D.C. Google Scholar
Bruss, F. T. and Ferguson, T. S. (1993) Minimizing the expected rank with full information J. Appl. Prob. 30, 616–626.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
Gilbert, J. and Mosteller, F. (1966) Recognizing the maximum of a sequence. J. Amer. Statist. Assoc. 61, 35–73.CrossRefGoogle Scholar
Hill, T. P. and Kennedy, D. P. (1992) Sharp inequalities for optimal stopping based on ranks. Ann. Appl. Prob. 2, 503–517.CrossRefGoogle Scholar
Kennedy, D. P. and Kertz, R. P. (1991) The asymptotic behavior of the reward sequence in the optimal stopping of i.i.d. random variables. Ann. Prob. 19, 329–341.Google Scholar
Lindley, D. V. (1961) Dynamic programming and decision theory. Appl. Statist. 10, 39–51,.Google Scholar
Moser, L. (1956) On a problem of Cayley. Scripta Mathematica 22, 289–292.Google Scholar
Troutman, J. L. (1983) Variational Calculus with Elementary Convexity. Springer, New York.Google Scholar