The secretary problem and the 37% rule
Need a hint?
Look at the first r candidates without hiring, then hire the first one better than all of them. Find the best r.
Skip the first 37 or 38 of 100 candidates and take the next one who beats them all: the chance of the best is about 37% (1/e).
How to work it out
Skip the first candidates, then take the first one better than everyone seen so far. If the best is at position , you win when the best of the first is among the first , which has probability :
(1)For this is largest at , with . For large put : , maximal at :
(2)The rule: reject the first 37% of candidates, then pick the next one who beats all of them. You get the best candidate more than a third of the time, however many there are.
LaTeX source of the formulas on this page
\[ \text{skip }37\%,\ \text{then take the next best}:\ P\approx0.368 \]
\[ P(r)=\frac{r-1}{n}\sum_{k=r}^{n}\frac1{k-1} \]
\[ P_{\max}\approx\frac1e\approx0.368 \]Questions
What is the answer to: The secretary problem and the 37% rule?
Skip the first 37 or 38 of 100 candidates and take the next one who beats them all: the chance of the best is about 37% (1/e).
What is the key idea?
Learning phase then commitment: the optimum balances missing the best against stopping too early.
Is there a hint?
Look at the first r candidates without hiring, then hire the first one better than all of them. Find the best r.