Solution
The Secretary Problem
Show the problem again
You interview n candidates sequentially. After each interview you must immediately accept or reject; you cannot go back. Using the optimal stopping rule (reject the first n/e candidates, then hire the next one who is better than all previous), what is the probability of hiring the best candidate as n → ∞? Express your answer as a fraction or decimal rounded to 4 decimal places.
Worked solution
The answer is 1/e ≈ 0.3679. The optimal strategy is to observe and reject the first ⌊n/e⌋ candidates to establish a benchmark, then hire the first candidate who beats all previous ones. As n grows, the probability of selecting the best candidate converges to exactly 1/e (about 37%).
Source: The secretary problem, popularised by Martin Gardner in Scientific American (1960); solved by Dennis Lindley (1961). Statement written for AxiomIQ.