Secretary problem
best choice problem, marriage problem
One of the best known optimal stopping problems (see also Stopping time; Sequential analysis).
A manager has the problem of selecting a secretary from a group of girls. He interviews them sequentially, one at a time, and, at each moment, can hire that particular girl. Rejected girls cannot be recalled. At each stage he knows how the present girl ranks with respect to her predecessors, but he does not know, of course, how she compares with the girls yet unseen. A rule is asked for that maximizes the chance of actually selecting the best girl.
The solution (for large ) is to examine and reject
girls and to subsequentially choose the first girl that is better than all these
girls, where the natural number
is chosen such that the fraction
is as close as possible to
(with
the base of the natural logarithms; see also
(number)). More precisely,
should be chosen to maximize the expression
![]() |
Seen as a betting game, the secretary problem is the same as the game of googol (see also Googol).
References
[a1] | Y.S. Chow, H. Robbins, D. Siegmund, "The theory of optimal stopping" , Dover, reprint (1991) (Orignal: Houghton–Mifflin, 1971) |
[a2] | T.S. Ferguson, "Who solved the secretary problem?" Statistical Science , 4 (1989) pp. 282–296 |
[a3] | P.R. Freeman, "The secretary problem and its extensions: a review" Internat. Statist. Review , 51 (1983) pp. 189–206 |
Secretary problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Secretary_problem&oldid=29864