Namespaces
Variants
Actions

Difference between revisions of "Secretary problem"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (correction)
 
(2 intermediate revisions by one other user not shown)
Line 1: Line 1:
 +
{{TEX|done}}
 
''best choice problem, marriage problem''
 
''best choice problem, marriage problem''
  
 
One of the best known optimal stopping problems (see also [[Stopping time|Stopping time]]; [[Sequential analysis|Sequential analysis]]).
 
One of the best known optimal stopping problems (see also [[Stopping time|Stopping time]]; [[Sequential analysis|Sequential analysis]]).
  
A manager has the problem of selecting a secretary from a group of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120060/s1200601.png" /> 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.
+
A manager has the problem of selecting a secretary from a group of $n$ 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120060/s1200602.png" />) is to examine and reject <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120060/s1200603.png" /> girls and to subsequentially choose the first girl that is better than all these <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120060/s1200604.png" /> girls, where the natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120060/s1200605.png" /> is chosen such that the fraction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120060/s1200606.png" /> is as close as possible to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120060/s1200607.png" /> (with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120060/s1200608.png" /> the base of the natural logarithms; see also [[E-number|<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120060/s1200609.png" /> (number)]]). More precisely, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120060/s12006010.png" /> should be chosen to maximize the expression
+
The solution (for large $n$) is to examine and reject $p$ girls and to subsequentially choose the first girl that is better than all these $p$ girls, where the natural number $p$ is chosen such that the fraction $\frac{p}{n}$ is as close as possible to $e^{-1}$ (with $e$ the base of the natural logarithms; see also [[E-number|$e$ (number)]]). More precisely, $p$ should be chosen to maximize the expression
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120060/s12006011.png" /></td> </tr></table>
+
\[\frac{p}{n}\sum_{k=p}^{n-1} \frac{1}{k}\]
  
 
Seen as a betting game, the secretary problem is the same as the game of googol (see also [[Googol|Googol]]).
 
Seen as a betting game, the secretary problem is the same as the game of googol (see also [[Googol|Googol]]).
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  Y.S. Chow,  H. Robbins,  D. Siegmund,  "The theory of optimal stopping" , Dover, reprint  (1991)  (Orignal: Houghton–Mifflin, 1971)</TD></TR>
+
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  Y.S. Chow,  H. Robbins,  D. Siegmund,  "The theory of optimal stopping" , Dover, reprint  (1991)  (Original: Houghton–Mifflin, 1971)</TD></TR>
 
<TR><TD valign="top">[a2]</TD> <TD valign="top"> T.S. Ferguson,  "Who solved the secretary problem?"  ''Statistical Science'' , '''4'''  (1989)  pp. 282–296</TD></TR>
 
<TR><TD valign="top">[a2]</TD> <TD valign="top"> T.S. Ferguson,  "Who solved the secretary problem?"  ''Statistical Science'' , '''4'''  (1989)  pp. 282–296</TD></TR>
 
<TR><TD valign="top">[a3]</TD> <TD  valign="top">  P.R. Freeman,  "The secretary problem and its  extensions: a review"  ''Internat. Statist. Review'' , '''51'''  (1983)  pp. 189–206</TD></TR></table>
 
<TR><TD valign="top">[a3]</TD> <TD  valign="top">  P.R. Freeman,  "The secretary problem and its  extensions: a review"  ''Internat. Statist. Review'' , '''51'''  (1983)  pp. 189–206</TD></TR></table>

Latest revision as of 18:52, 11 December 2020

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 $n$ 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 $n$) is to examine and reject $p$ girls and to subsequentially choose the first girl that is better than all these $p$ girls, where the natural number $p$ is chosen such that the fraction $\frac{p}{n}$ is as close as possible to $e^{-1}$ (with $e$ the base of the natural logarithms; see also $e$ (number)). More precisely, $p$ should be chosen to maximize the expression

\[\frac{p}{n}\sum_{k=p}^{n-1} \frac{1}{k}\]

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) (Original: 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
How to Cite This Entry:
Secretary problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Secretary_problem&oldid=29863
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article