The ``thirty-seven percent rule and the secretary problem with relative ranks

DOI10.7151/DMPS.1161zbMATH Open1401.62128arXiv1512.02996OpenAlexW2963200711MaRDI QIDQ5262800FDOQ5262800

Svetoslav Semov, Bajnok, Béla

Publication date: 16 July 2015

Published in: Discussiones Mathematicae Probability and Statistics (Search for Journal in Brave)

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 $ksimn/mathrme$, 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$.

Full work available at URL: https://arxiv.org/abs/1512.02996

Recommendations

• The secretary problem of minimizing the expected rank: a simple suboptimal approach with generalizations
• Probabilities of choosing applicants of arbitrary rank in the secretary problem
• The secretary problem: minimizing the expected rank with I.I.D. random variables
• Publication:4734631
• Remarks on the Secretary Problem

zbMATH Keywords

optimizationstopping ruleoptimal stoppingsecretary problemrelative ranksbest choice

Mathematics Subject Classification ID

Combinatorial probability (60C05) Stopping times; optimal stopping problems; gambling theory (60G40) Optimal stopping in statistics (62L15)

This page was built for publication: The ``thirty-seven percent rule and the secretary problem with relative ranks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5262800)