Remarks on the secretary problem.

*(English)*Zbl 0749.62053The classical secretary problem is considered: A given number of candidates are to be interviewed for a certain position. They present themselves one by one in random order. We can either hire the \(i\)-th candidate according to the (relative) rank among those candidates already interviewed, in which case the process stops, or go on to the next, in which case the \(i\)-th cannot be recalled. One of the candidates has to be selected. If the (absolute) rank of the selected one among all candidates is \(x\), our loss will be \(f(x)\), where \(f\) is a real function defined on the positive integers. We want to choose a stopping rule that will minimize the expected loss (asymptotically as \(n\to\infty\)).

The following loss functions are dealt with: \(f(x) = 0\) if \(x=1\) and \(f(x)=1\) otherwise; \(f(x)=x\); and \(f(x)=x(x+1)\cdots (x+a-1)\) with some integer \(a\geq 1\). In the latter case, by some “heroic heuristics” the problem is reduced to solving a simple differential equation. Using the same argument, the case \(f(x)=x^ 2\) is also studied. Finally, a slightly modified problem is investigated: Instead of appearing one by one in random order, in each step only the best and the worst of the remaining candidates are assumed to show with probability 1/2 each.

The following loss functions are dealt with: \(f(x) = 0\) if \(x=1\) and \(f(x)=1\) otherwise; \(f(x)=x\); and \(f(x)=x(x+1)\cdots (x+a-1)\) with some integer \(a\geq 1\). In the latter case, by some “heroic heuristics” the problem is reduced to solving a simple differential equation. Using the same argument, the case \(f(x)=x^ 2\) is also studied. Finally, a slightly modified problem is investigated: Instead of appearing one by one in random order, in each step only the best and the worst of the remaining candidates are assumed to show with probability 1/2 each.

Reviewer: V.Mammitzsch (Marburg)

##### MSC:

62L15 | Optimal stopping in statistics |

60G40 | Stopping times; optimal stopping problems; gambling theory |

PDF
BibTeX
XML
Cite

\textit{H. Robbins}, Am. J. Math. Manage. Sci. 11, No. 1--2, 25--37 (1991; Zbl 0749.62053)

Full Text:
DOI

##### References:

[1] | Chow Y.S., Israel Jour. Math. 2 pp 81– (1964) · Zbl 0149.14402 · doi:10.1007/BF02759948 |

[2] | Chow Y.S., Great Expectations (1971) |

[3] | Mucci A.G., Ann. Prob. 1 pp 417– (1973) · Zbl 0261.60036 · doi:10.1214/aop/1176996936 |

[4] | An extensive bibliography is given in. |

[5] | Ferguson T.S., Statistical Science 4 pp 282– (1989) · doi:10.1214/ss/1177012493 |

[6] | There is a large and growing literature on the secretary problem in its various modifications. Two papers not mentioned in [4] are. |

[7] | Dhariyal I.D., Journ. Am. Statist. Assn. 76 pp 952– (1981) · doi:10.1080/01621459.1981.10477748 |

[8] | Rubin H., Ann. Of Prob. 5 pp 627– (1977) · Zbl 0381.60036 · doi:10.1214/aop/1176995774 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.