Remarks on the Secretary Problem

From MaRDI portal





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.




Cited in
(42)








This page was built for publication: Remarks on the Secretary Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3988370)