Secretary problem

From Wikipedia, the free encyclopedia

In statistics and game theory, the secretary problem (also known as the marriage problem, the optimal stopping problem, the sultan's dowry problem or the fussy suitor problem) is a puzzle involving being presented sequentially with a known number of items of varying quality. The puzzle is to select the best one from the items on offer; but rejecting an item is irrevocable. Because of the random element, the problem is often phrased in terms of maximizing the probability of choosing the best on offer.

The canonical example is an organization wishing to hire a secretary. Applicants present themselves sequentially; the interviewers may rank the applicants, and can remember the quality of everyone whom they have interviewed. The interviewers must accept or reject each applicant immediately after the interview, however. If an applicant is rejected, that person will find another job and become unavailable for hire. Other light-hearted instantiations include choosing a spouse from a series of suitors.

The problem stated above has a very simple optimal strategy: for some integer $r$ with $1\leq r<n$ , examine and reject the first $r$ applicants. Then, from the remaining $n - r$ applicants, choose the first one that is best seen to date. Optimization techniques may be used to determine the most efficacious value for $r$ ; in the limiting case of large $n$ , it may be shown that $r\approx n/e \approx 0.368n$ where $e$ is the base of natural logarithms. With this strategy, the probability of finding the best option is $1 / e$ (about 36.8%).

The problem as stated above has many variants, including:

The chooser may be allowed to choose two items rather than one
The number of applicants may be unknown
Ties in applicants may be significant
Rejectees may be recalled
The chooser may be satisfied with second best

[edit] Optimal $r$ derivation

In the optimal strategy for $n$ suitors, there are two suitors which are relevant. One is the best suitor, which we shall label as the $a$ th suitor, and the other one is the second-best suitor in the interval $[1, a$ ].

Given $a$ : If $a \le r$ , you would reject the best suitor and fail. If $a > r$ , the strategy divides the suitors into three groups, $[1, r$ ], $(r, a$ ] and $(a, n$ ]. For the strategy to succeed, the second-best suitor in the interval $[1, a$ ] has to be in $[1, r$ ] (otherwise he will be accepted before the best suitor). The probability of that is $\frac{r}{a-1}$ (since $a$ -th position is occupied by the best suitor). Therefore, the overall chance of success is $\frac{r}{a-1}$ given that $a > r$ .