The secretary problem: minimizing the expected rank with I.I.D. random variables
David Assaf, Ester Samuel‐Cahn · Advances in Applied Probability · 1996
n candidates, represented by n i.i.d. continuous random variables X 1 , …, X n with known distribution arrive sequentially, and one of them must be chosen, using a non-anticipating stopping rule. The objective is to minimize the expected rank (among the ranks of X 1 , …, X n ) of the candidate chosen, where the best candidate, i.e. the one with smallest X -value, has rank one, etc. Let the value of the optimal rule be V n , and lim V n = V. We prove that V > 1.85. Limiting consideration to the class of threshold rules of the form t n = min { k : X k ≦ a k for some constants a k , let W n be the value of the expected rank for the optimal threshold rule, and lim W n = W . We show 2.295 < W < 2.327.