The "Thirty-seven Percent Rule" and the Secretary Problem with Relative Ranks

preprint2015arXivOpen access

Abstract

We revisit the problem of selecting an item from nn 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 kk items and then select the first subsequent item that ranks lower than the ll-th lowest-ranked item among the first kk. We prove that the optimal rule has k∼n/ek \sim n/{\mathrm e}, as in the classical secretary problem where our sole objective is to select the item of lowest rank; however, with the optimally chosen ll, here we can get the expected rank of the item selected to be less than any positive power of nn (as nn 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 dd.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.