Posted by: sclee09 | November 28, 2008

## The Secretary Problem

I was sitting warm and snug in my bed, full from Thanksgiving dinner and doing some reading for my Lit-A class (Dante).  I suddenly leapt out of bed because I had a very bad feeling that I had a blog post due sometime right around now (in fact, yesterday).  So, I’m very sorry for the delay…

The Secretary Problem is a pretty famous probability problem, introduced by Merrill M. Flood in 1949.  It has a few other names, among them the marriage problem, the fiance problem, and the best choice problem.  Here it is:

1. There is a single secretarial position to fill.
2. There are n applicants for the position, and the value of n is known.
3. The applicants can be ranked from best to worst with no ties.
4. The applicants are interviewed sequentially in a random order, with each order being equally likely.
5. After each interview, the applicant is accepted or rejected.
6. The decision to accept or reject an applicant can be based only on the relative ranks of the applicants interviewed so far.
7. Rejected applicants cannot be recalled.
8. The object is to select the best applicant. The payoff is 1 for the best applicant and zero otherwise.

Interestingly, psychologists have conducted real-life experiments of the secretary problem, and people tend to stop searching too soon.  Ah, a mathematical justification for a nonexistent dating life to the grandparents 🙂