# The "Thirty-seven Percent Rule" and the secretary problem with relative ranks

• Volume: 34, Issue: 1-2, page 5-21
• ISSN: 1509-9423

top

## Abstract

top
We revisit the problem of selecting an item from n choices that appear before us in random sequential order so as to minimize the expected rank of the item selected. In particular, we examine the stopping rule where we reject the first k items and then select the first subsequent item that ranks lower than the l-th lowest-ranked item among the first k. We prove that the optimal rule has k ~ n/e, as in the classical secretary problem where our sole objective is to select the item of lowest rank; however, with the optimally chosen l, here we can get the expected rank of the item selected to be less than any positive power of n (as n approaches infinity). We also introduce a common generalization where our goal is to minimize the expected rank of the item selected, but this rank must be within the lowest d.

## How to cite

top

Béla Bajnok, and Svetoslav Semov. "The "Thirty-seven Percent Rule" and the secretary problem with relative ranks." Discussiones Mathematicae Probability and Statistics 34.1-2 (2014): 5-21. <http://eudml.org/doc/270923>.

@article{BélaBajnok2014,
abstract = {We revisit the problem of selecting an item from n choices that appear before us in random sequential order so as to minimize the expected rank of the item selected. In particular, we examine the stopping rule where we reject the first k items and then select the first subsequent item that ranks lower than the l-th lowest-ranked item among the first k. We prove that the optimal rule has k ~ n/e, as in the classical secretary problem where our sole objective is to select the item of lowest rank; however, with the optimally chosen l, here we can get the expected rank of the item selected to be less than any positive power of n (as n approaches infinity). We also introduce a common generalization where our goal is to minimize the expected rank of the item selected, but this rank must be within the lowest d.},
author = {Béla Bajnok, Svetoslav Semov},
journal = {Discussiones Mathematicae Probability and Statistics},
keywords = {secretary problem; relative ranks; stopping rule; optimization; best choice; optimal stopping},
language = {eng},
number = {1-2},
pages = {5-21},
title = {The "Thirty-seven Percent Rule" and the secretary problem with relative ranks},
url = {http://eudml.org/doc/270923},
volume = {34},
year = {2014},
}

TY - JOUR
AU - Béla Bajnok
AU - Svetoslav Semov
TI - The "Thirty-seven Percent Rule" and the secretary problem with relative ranks
JO - Discussiones Mathematicae Probability and Statistics
PY - 2014
VL - 34
IS - 1-2
SP - 5
EP - 21
AB - We revisit the problem of selecting an item from n choices that appear before us in random sequential order so as to minimize the expected rank of the item selected. In particular, we examine the stopping rule where we reject the first k items and then select the first subsequent item that ranks lower than the l-th lowest-ranked item among the first k. We prove that the optimal rule has k ~ n/e, as in the classical secretary problem where our sole objective is to select the item of lowest rank; however, with the optimally chosen l, here we can get the expected rank of the item selected to be less than any positive power of n (as n approaches infinity). We also introduce a common generalization where our goal is to minimize the expected rank of the item selected, but this rank must be within the lowest d.
LA - eng
KW - secretary problem; relative ranks; stopping rule; optimization; best choice; optimal stopping
UR - http://eudml.org/doc/270923
ER -

## References

top
1. [1] J. Bearden, A new secretary problem with rank-based selection and cardinal payoffs, J. Math. Psych. 50 (2006) 58-59. doi: 10.1016/j.jmp.2005.11.003 Zbl1125.90028
2. [2] F. Bruss and T. Ferguson, Minimizing the expected rank with full information, J. Appl. Prob. 30 (1993) 616-626. doi: 10.2307/3214770 Zbl0781.60035
3. [3] Y. Chow, S. Moriguti, H. Robbins and S. Samuels, Optimal selection based on relative ranks, Israel J. Math. 2 (1964) 81-90. Zbl0149.14402
4. [4] T. Ferguson, Who solved the secretary problem?, Statist. Sci. 4 (1989) 282-296. doi: 10.1214/ss/1177012493 Zbl0788.90080
5. [5] P. Freeman, The secretary problem and its extensions - A review, Internat. Statist. Rev. 51 (1983) 189-206. Zbl0516.62081
6. [6] J. Gilbert and F. Mosteller, Recognizing the maximum of a sequence, J. Amer. Statist. Assoc. 61 (1966) 35-73. doi: 10.2307/2283044
7. [7] A. Krieger and E. Samuel-Cahn, The secretary problem of minimizing the expected rank: a simple suboptimal approach with generalizations, Adv. Appl. Prob. 41 (2009) 1041-1058. doi: 10.1239/aap/1261669585 Zbl1186.62101
8. [8] D.V. Lindley, Dynamic programming and decision theory, Appl. Statistics 10 (1961) 39-51. doi: 10.2307/2985407 Zbl0114.34904
9. [9] D. Pfeifer, Extremal processes, secretary problems and the 1/e law, J. Appl. Prob. 26 (1989) 722-733. Zbl0693.60030

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.