Hostname: page-component-745bb68f8f-hvd4g Total loading time: 0 Render date: 2025-02-05T22:55:47.293Z Has data issue: false hasContentIssue false
  • English
  • Français

OPTIMAL SELECTION OF THE k-TH BEST CANDIDATE

Published online by Cambridge University Press:  10 April 2019

Yi-Shen Lin ,
Shoou-Ren Hsiau  and
Yi-Ching Yao
Yi-Shen Lin
Affiliation:
Institute of Statistical Science, Academia Sinica, Taipei 115 Taiwan, R.O.C E-mail: yslin@stat.sinica.edu.tw
Shoou-Ren Hsiau
Affiliation:
Department of Mathematics, National Changhua University of Education, No. 1, Jin-De Rd., Changhua 500 Taiwan, R.O.C. E-mail: srhsiau@cc.ncue.edu.tw
Yi-Ching Yao
Affiliation:
Institute of Statistical Science, Academia Sinica, Taipei 115 Taiwan, R.O.C. E-mail: yao@stat.sinica.edu.tw
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.

In the subject of optimal stopping, the classical secretary problem is concerned with optimally selecting the best of n candidates when their relative ranks are observed sequentially. This problem has been extended to optimally selecting the kth best candidate for k ≥ 2. While the optimal stopping rule for k=1,2 (and all n ≥ 2) is known to be of threshold type (involving one threshold), we solve the case k=3 (and all n ≥ 3) by deriving an explicit optimal stopping rule that involves two thresholds. We also prove several inequalities for p(k, n), the maximum probability of selecting the k-th best of n candidates. It is shown that (i) p(1, n) = p(n, n) > p(k, n) for 1<k<n, (ii) p(k, n) ≥ p(k, n + 1), (iii) p(k, n) ≥ p(k + 1, n + 1) and (iv) p(k, ∞): = lim n→∞p(k, n) is decreasing in k.

Keywords

backward inductionbest choiceoptimal stoppingsecretary problem
Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 33 , Issue 3 , July 2019 , pp. 327 - 347
Copyright
Copyright © Cambridge University Press 2019 

References

1Chow, Y.-S., Robbins, H., & Siegmund, D. (1971). Great expectations: the theory of optimal stopping. Boston, MA: Houghton Mifflin.Google Scholar
2Ferguson, T.S. (1989). Who solved the secretary problem? Statistical Science 4: 282–296.Google Scholar
3Ferguson, T.S. (2008). Optimal stopping and applications. Mathematics Department, UCLA, http://www.math.ucla.edu/~tom/Stopping/Contents.html.Google Scholar
4Freeman, P.R. (1983). The secretary problem and its extensions: a review. International Statistical Review 51: 189–206.Google Scholar
5Graham, R., Knuth, D., & Patashnik, O. (1994). Concrete mathematics: a foundation for computer science. Reading, MA: Addison-Wesley Publishing Company.Google Scholar
6Lindley, D.V. (1961). Dynamic programming and decision theory. Applied Statistics 10: 39–51.Google Scholar
7Rose, J.S. (1982). A problem of optimal choice and assignment. Operational Research 30: 172–181.Google Scholar
8Rose, J.S. (1982). Selection of nonextremal candidates from a sequence. Journal of Optimization Theory and Application 38: 207–219.Google Scholar
9Samuels, S.M. (1991). Secretary problems. In Ghosh, B.K. and Sen, P.K. (eds.), Handbook of sequential analysis, (Statistics Textbooks Monographs, Vol. 118), New York: Marcel Dekker, pp. 381–405.Google Scholar
10Suchwalko, A. & Szajowski, K. (2002). Non standard, no information secretary problems. Scientiae Mathematicae Japonicae 56: 443–456.Google Scholar
11Szajowski, K. (1982). Optimal choice problem of a-th object. Mat. Stos 19: 51–65 (in Polish).Google Scholar
12Vanderbei, R.J. (2012). The postdoc variant of the secretary problem. Technical Report. http://www.princeton.edu/~rvdb/tex/PostdocProblem/PostdocProb.pdf.Google Scholar