Exact results for a secretary problem

Abstract

We consider the following secretary problem: items ranked from 1 to n are randomly selected without replacement, one at a time, and to ‘win' is to stop at an item whose overall rank is less than or equal to s , given only the relative ranks of the items drawn so far. Our method of analysis is based on the existence of an imbedded Markov chain and uses the technique of backwards induction. In principal the approach can be used to give exact results for any value of s ; we do the working for s = 3. We give exact results for the optimal strategy, the probability of success and the distribution of T , and the total number of draws when the optimal strategy is implemented. We also give some asymptotic results for these quantities as n → ∞.