Secretary problem  From Wikipedia, the free encyclopedia Jump
to: navigation, search  The secretary problem is one of many
names for a famous problem of the optimal stopping theory. The
problem has been studied extensively in the fields of applied
probability, statistics, and decision theory. It is also known
as the marriage problem, the sultan's dowry problem, the fussy
suitor problem, the googol game, and the best choice problem.
The basic form of the problem is the following: imagine an
administrator willing to hire the best secretary out of n
rankable applicants for a position. The applicants are
interviewed one by one in random order. A decision about each
particular applicant is to be made immediately after the
interview. Once rejected, an applicant cannot be recalled.
During the interview, the administrator can rank the applicant
among all applicants interviewed so far, but is unaware of the
quality of yet unseen applicants. The question is about the
optimal strategy (stopping rule) to maximize the pr