When to stop looking
Tonight's idea
You see \(n\) candidates one at a time, in random order. After each you hire or reject, and a rejection is final. You cannot score them, only compare: is this the best so far? You win only by hiring the best of all \(n\). This is the secretary problem.
Hiring the first is a \(1/n\) shot. Better: let the first \(r\) go by, then hire the next one who beats everyone seen so far. The first \(r\) set the bar.
The best sits at position \(j\) with probability \(1/n\). The rule hires her if \(j > r\) and nobody at positions \(r+1\) to \(j-1\) cleared the bar, i.e. the best of the first \(j-1\) is among the first \(r\): probability \(r/(j-1)\). Summing over \(j\),
\(P(r) = \dfrac1n\displaystyle\sum_{j=r+1}^{n}\frac{r}{j-1} = \frac{r}{n}\Big(\frac1r + \frac1{r+1} + \cdots + \frac1{n-1}\Big).\)
For large \(n\) put \(x = r/n\); the bracket is a harmonic slice, about \(\ln(n/r) = -\ln x\). So \(P \approx -x\ln x\), whose derivative \(-\ln x - 1\) vanishes at \(x = 1/e \approx 0.37\), where \(P = 1/e\). Skip 37%, then take the next best: a 37% chance of the very best, for any \(n\).
Watch one: \(n = 10\)
\(n/e = 3.7\), so try \(r = 3\): \(P(3) = \tfrac{3}{10}\big(\tfrac13 + \tfrac14 + \cdots + \tfrac19\big) = \tfrac{3349}{8400} = 0.3987\). Neighbours:
| \(r\) | 0 | 1 | 2 | 3 | 4 | 5 | 9 |
|---|---|---|---|---|---|---|---|
| \(P(r)\) | 0.100 | 0.283 | 0.366 | 0.399 | 0.398 | 0.373 | 0.100 |
A simulation of 200,000 random orderings with \(r = 3\) hired the best 39.9% of the time, matching the formula. Note how flat the top is: \(r = 3\) and \(r = 4\) are almost equally good.
Play the game yourself, then let the computer try every cut-off: mathdetours.com/demos/secretary.html.
Your turn
- \(n = 4\). Compute \(P(r)\) for \(r = 0, 1, 2, 3\) as exact fractions. Which \(r\) is best, and how does it compare with \(n/e\)?
- Show from the formula that \(P(n-1) = 1/n\), the same as \(P(0)\). Then explain each in one sentence, without the formula.
- Let \(h(x) = -x\ln x\) on \(0 \lt x \le 1\). Using the product rule and \((\ln x)' = 1/x\), find \(h'(x)\), solve \(h'(x) = 0\), check with \(h''\) that it is a maximum, and find the maximum value.
- The 37% rule can fail in two ways. (a) What is the probability that the best candidate is among the first \(r\) rejected? What is it in the limit? (b) When that happens, who do you end up hiring, and why? (c) The other failure is hiring someone who cleared the bar but was not the best. Find its limiting probability.
Stretch: what seeing the scores is worth
Suppose you see each candidate's score, uniform between 0 and 1, and \(n = 2\). Rule: hire the first if her score exceeds \(t\), else take the second. Find the success probability in terms of \(t\), the best \(t\) and the best success rate. Compare with the rank-only rule's \(1/2\).
Answers
- \(P(0) = \tfrac14\), \(P(1) = \tfrac14\big(1 + \tfrac12 + \tfrac13\big) = \tfrac{11}{24}\), \(P(2) = \tfrac24\big(\tfrac12 + \tfrac13\big) = \tfrac{5}{12}\), \(P(3) = \tfrac34 \cdot \tfrac13 = \tfrac14\). Best is \(r = 1\) with \(11/24 \approx 0.458\); \(n/e = 1.47\), so rounding down was right.
- \(P(n-1) = \tfrac{n-1}{n}\cdot\tfrac{1}{n-1} = \tfrac1n\). With \(r = 0\) you hire the first candidate, who is the best with probability \(1/n\). With \(r = n-1\) you reject everyone but the last and are forced to take her, also the best with probability \(1/n\).
- \(h'(x) = -\ln x - x\cdot\tfrac1x = -\ln x - 1 = 0\) at \(x = e^{-1}\). \(h''(x) = -1/x \lt 0\), a maximum. \(h(1/e) = -\tfrac1e \ln\tfrac1e = \tfrac1e \approx 0.368\).
- (a) \(r/n\), which tends to \(1/e \approx 0.37\). (b) The bar is now unbeatable, nobody clears it, and you are forced to hire the last candidate, whoever she is. (c) Total failure is \(1 - 1/e\); subtract the \(1/e\) from (a): \(1 - 2/e \approx 0.26\). So the rule wins 37%, hires a runner-up of some kind 26%, and gets stuck with the last candidate 37% of the time.
Stretch. Let the scores be \(x\) then \(y\). You win if \(x > t\) and \(x > y\), probability \(\int_t^1 x\,dx = \tfrac12 - \tfrac{t^2}{2}\), or if \(x \le t\) and \(y > x\), probability \(\int_0^t (1 - x)\,dx = t - \tfrac{t^2}{2}\). Total \(\tfrac12 + t - t^2\), maximised at \(t = \tfrac12\) with value \(\tfrac34\). Knowing the scale, not just the order, lifts the odds from \(1/2\) to \(3/4\). The 37% rule assumes you know nothing about the scale, and that the order is random.