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

• Autorzy: Béla Bajnok , Svetoslav Semov
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

secretary problem; relative ranks; stopping rule; optimization

Kategorie tematyczne

• 62L99: None of the above, but in this section
• 60C05: Combinatorial probability

• Wydawca: Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra
• Czasopismo: Discussiones Mathematicae Probability and Statistics
• Rocznik: 2014
• Tom: 34
• Numer: 1-2
• Strony: 5-21

Daty

wydano

2014

otrzymano

2013-09-11

Twórcy

autor

Béla Bajnok

• Department of Mathematics, Gettysburg College, 300 N. Washington Street, Gettysburg, PA 17325-1486 USA

autor

Svetoslav Semov

• Department of Economics, Boston University, 270 Bay State Rd, Boston, MA 02215 USA

Bibliografia

• [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
• [2] F. Bruss and T. Ferguson, Minimizing the expected rank with full information, J. Appl. Prob. 30 (1993) 616-626. doi: 10.2307/3214770
• [3] Y. Chow, S. Moriguti, H. Robbins and S. Samuels, Optimal selection based on relative ranks, Israel J. Math. 2 (1964) 81-90.
• [4] T. Ferguson, Who solved the secretary problem?, Statist. Sci. 4 (1989) 282-296. doi: 10.1214/ss/1177012493
• [5] P. Freeman, The secretary problem and its extensions - A review, Internat. Statist. Rev. 51 (1983) 189-206.
• [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] 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
• [8] D.V. Lindley, Dynamic programming and decision theory, Appl. Statistics 10 (1961) 39-51. doi: 10.2307/2985407
• [9] D. Pfeifer, Extremal processes, secretary problems and the 1/e law, J. Appl. Prob. 26 (1989) 722-733.

Identyfikatory

DOI

10.7151/dmps1161