The Secretary Problem

For some reason that I’m not quite sure of, I remembered an interesting mathematical probability problem I first read about many years ago. It’s called the Secretary Problem.

Suppose you have 100 job applicants for the position of your secretary. You don’t know which applicant is the best one, and you don’t want to interview all 100 applicants. After each interview, you must immediately decide to hire the applicant, or reject the applicant and move on to the next applicant. What is some reasonable rule you can use?

In the theory of this problem, the term Candidate is the best applicant seen to date. Suppose you decide to interview until you’ve seen 2 Candidates, then take the next Candidate.

For example, suppose each applicant has (unknown to you) a rating of 1 through 100, with 1 being best. And suppose the order of the ratings of the applicant interviews is:

[5, 100 (worst), 3, 4, 2, 8, 1 (best), 7, 6, . . ] 

You would interview the first applicant. Their rating is 5 and they’d be Candidate #1 and you reject them. The second applicant gets a rating of 100 so they aren’t a Candidate and you move on. You interview the third secretary applicant and she gets a rating of 3 and so she is Candidate #2 and you move on. You will now take the next Candidate encountered. The fourth applicant gets a rating of 4, is not a Candidate, and you move on. The fifth applicant gets a rating of 2 is a Candidate and you accept her. (You never know about the remaining applicants, including the best one who would have come 2 interviews later).

There is a lot of fascinating math behind the Secretary Problem, and a lot of potential rules you can try. It turns out a good strategy is to reject the first n/e applicants then take the next Candidate, where n is the number of applicants and e is the math constant 2.718. So for 100 applicants you’d reject the first 100/2.718 = 37 applicants (while tracking Candidates) and take the next Candidate.

This entry was posted in Machine Learning. Bookmark the permalink.