The secretary problem, also called the best-choice problem or marriage problem, is an optimal stopping problem in which 
distinctly ranked candidates are presented in an order given
by a random permutation. After each interview,
the interviewer knows only the candidate's relative rank among those already seen
and must either accept that candidate or reject the candidate permanently. The objective
is to maximize the probability of selecting the best
candidate.
Suppose the first 
candidates are rejected and the first later candidate better than all of them is
accepted. The probability that this rule selects
the best candidate is
 |
For large 
,
writing 
gives the approximation 
. This is maximized at 
, so the optimal rule asymptotically rejects the first
candidates and then accepts the next
record. Its limiting success probability is also
(Freeman 1983, Ferguson 1989).
This use of "marriage problem" is distinct from Hall's marriage theorem, which concerns the existence of a matching, and from the stable marriage problem, which concerns stability under two sets of preference rankings.
