Optimal Stopping and the 1/e Rule for the Secretary Problem

Scenario

An interviewer seeks to hire the single best secretary from a pool of $n$ candidates arriving in random order. Candidates can be strictly ranked from 1 (best) to $n$ (worst) with no ties. All $n!$ arrival permutations are equally likely. After interviewing candidate $k$, the interviewer must immediately decide whether to hire or permanently reject them. Payoff is 1 if the overall best candidate is selected, and 0 otherwise.

Your Task

1. Prove that the optimal policy is a threshold rule: reject the first $r-1$ candidates, then hire the first candidate who is better than all previous candidates.
2. Derive the exact finite-$n$ success probability $P_n(r)$.
3. Take the asymptotic limit $n \to \infty$ with $x = r/n$ to show $P(x) = -x \ln x$.
4. Determine the optimal asymptotic threshold $x^*$ and the maximum hiring probability.

Constraints

• Uniform random permutation of rankings; no backward recall.

Examples For $n = 4$, optimal $r = 2$ with success probability $11/24 \approx 45.83\%$. As $n \to \infty$, $r^* \approx n/e$ with success probability $1/e \approx 36.79\%$.