The Secretary Problem
The Secretary Problem
The manager of a firm wants to hire a good secretary. He has applicants to interview sequentially, in random order, and can rank the ones interviewed so far. The manager is able to make a decision immediately after each interview. If an applicant is rejected, that applicant cannot be recalled.
n
The manager applies the following strategy. He first interviews applicants but rejects them all. From among the rest of the applicants, he then chooses the first one that is better than any of the initial set of applicants. If such an applicant does not exist, the last applicant is automatically chosen. The problem is to choose the size of the initial sample optimally, that is, in such a way as to maximize the probability of getting the best applicant. The best applicant has rank 1 and the worst applicant rank .
r
r
r
n
This Demonstration shows examples of this optimal stopping problem. The green bars in the first plot are the applicants in the initial sample: they are all rejected. The blue bars are the rest of the applicants, and the red bar is the applicant that will be chosen. The second plot shows the probabilities that the best applicant will be chosen if the initial sample contains various numbers of applicants; the black bar is the number chosen. The thick magenta bar represents the best solution: it maximizes the probability of getting the best applicant.
r