Remarks on the secretary problem. (English) Zbl 0749.62053

The 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.


62L15 Optimal stopping in statistics
60G40 Stopping times; optimal stopping problems; gambling theory
Full Text: DOI


[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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.