Secretary Problem (Optimal Stopping)

The secretary problem: You interview $n$ candidates sequentially. After each interview, you must immediately accept or reject (no callbacks). How do you maximize the probability of hiring the best? Optimal strategy: Reject the first $\lfloor n/e \rfloor$ candidates (observation phase). Then hire the first subsequent candidate who is better than all observed so far. Success probability: $\approx 1/e \approx 36.8\%$ for large $n$. Why $1/e$? Let $r$ be the cutoff. The probability that the best candidate is hired equals $\frac{r}{n} \sum_{k=r}^{n-1} \frac{1}{k}$. Optimizing over $r$ gives $r \approx n/e$ and probability $\approx 1/e$. Variations: - Minimize expected rank of hired candidate → different threshold - Multiple hires allowed → different strategy - Partial information → Bayesian updates When to use: Any optimal stopping problem where you see options sequentially and can't go back. House buying, job searching, parking problems.