Classical Secretary Problem: Proof and the 37% Rule
The Classical Secretary Problem
Why should you reject roughly the first 37% of candidates before choosing? The secretary problem is a classical optimal stopping problem: decisions are sequential, rejections are final, and success means selecting the single best candidate.
The exact finite-sample solution and its asymptotic 37% rule are derived below; you can also experiment with the rule.
The question in plain language
Suppose you interview 100 candidates in random order. After each interview, you know how that candidate compares with the people you have already met—but not how they compare with candidates you have not seen. You must decide immediately whether to hire them or reject them forever.
Would you hire a strong early candidate, or wait and risk losing everyone?
The classical strategy has two phases:
- Observe: Reject an initial group and note the best candidate in that group.
- Choose: Hire the first later candidate who is better than everyone interviewed so far. If no such candidate appears, you do not succeed.
For a large pool of candidates, the best observation period is approximately 37% of the total. With 100 candidates, that suggests observing about 37 first; the exact best integer cutoff comes from the finite-sample mathematics below.
This result depends on the assumptions of the model. It is not a universal recommendation for real hiring, dating, or investment decisions.
Model and assumptions
There are \(n\ge 2\) candidates, ranked absolutely from \(1\) (best) to \(n\) (worst). The classical no-information model assumes:
- The candidates arrive in a uniformly random order (all \(n!\) orders are equally likely).
- You observe only each candidate’s relative rank among those seen so far, not their absolute rank.
- You may accept at most one candidate. Every rejection is irrevocable.
- Your objective is to maximize the probability of choosing the single overall best candidate.
A candidate is a record if they are better than all candidates seen before. Since a nonrecord cannot be the overall best, there is no benefit to selecting one when the objective is the overall best.
The threshold strategy
Fix an integer \(r\) with \(0\le r<n\):
- Reject the first \(r\) candidates, observing their relative ranks.
- Starting at position \(r+1\), accept the first record (a candidate better than every earlier candidate).
- If there is no subsequent record, no candidate is selected and the attempt fails. (Requiring a selection at the final interview would not change the probability of selecting the overall best.)
For \(r=0\), the rule accepts the first candidate immediately. This convention is used in the interactive simulation below.
The classical theorem establishes that a threshold rule is optimal among all stopping rules based on relative ranks, not merely the best rule within a preselected class of thresholds. A backward-induction proof of this optimal-policy structure is provided on the Backward Induction page.
Exact success probability: a finite-\(n\) derivation
Let \(P_n(r)\) denote the probability that the threshold-\(r\) strategy selects absolute rank \(1\).
Proposition. For \(1\le r<n\),
\[ \boxed{ P_n(r)=\frac{r}{n}\sum_{k=r+1}^{n}\frac{1}{k-1} =\frac{r}{n}\left(H_{n-1}-H_{r-1}\right), } \]
where \(H_m=\sum_{j=1}^m 1/j\) for \(m\ge1\) and \(H_0=0\). For \(r=0\), \(P_n(0)=1/n\).
Proof. Write \(K\) for the arrival position of the overall best candidate. Uniform random order gives
\[ \Pr(K=k)=\frac1n,\qquad k=1,\ldots,n. \]
If \(K\le r\), that candidate is rejected, so success is impossible. If \(K=k>r\), the strategy selects the overall best precisely when the best candidate among the first \(k-1\) arrivals occurred during the initial \(r\) positions. Otherwise, a record after position \(r\) would have triggered selection earlier.
Conditionally on \(K=k\), each of the first \(k-1\) positions is equally likely to hold the best among those first \(k-1\) candidates. Thus
\[ \Pr(\text{success}\mid K=k)=\frac{r}{k-1},\qquad k>r. \]
Summing over the possible positions of the overall best gives
\[ P_n(r) =\sum_{k=r+1}^{n}\Pr(K=k)\Pr(\text{success}\mid K=k) =\frac{r}{n}\sum_{k=r+1}^{n}\frac{1}{k-1}. \]
If \(r=0\), the first candidate is accepted, which is the overall best with probability \(1/n\). \(\square\)
Which threshold is optimal for a given \(n\)?
Finite-\(n\) criterion. For \(1\le r<n-1\),
\[ \boxed{ P_n(r+1)-P_n(r) =\frac1n\left(\sum_{j=r+1}^{n-1}\frac1j-1\right). } \]
To see this, subtract the two formulas:
\[ \begin{aligned} nP_n(r+1)&=(r+1)\sum_{j=r+1}^{n-1}\frac1j,\\ nP_n(r)&=1+r\sum_{j=r+1}^{n-1}\frac1j. \end{aligned} \]
The sum in the difference decreases strictly as \(r\) increases. Consequently, the threshold probabilities increase while the sum exceeds \(1\), are equal at adjacent thresholds if the sum equals \(1\), and decrease once the sum falls below \(1\).
The boundary case \(r=0\) must be considered separately: for \(n\ge3\), \(P_n(1)=H_{n-1}/n>1/n=P_n(0)\), whereas for \(n=2\) the two probabilities are equal. Thus, for \(n\ge3\), the smallest optimal threshold is
\[ \boxed{ r_n^\star=\min\left\{r\in\{1,\ldots,n-1\}: \sum_{j=r+1}^{n-1}\frac1j\le1\right\}. } \]
An empty sum is \(0\). If the sum equals \(1\) at the transition and \(r_n^\star<n-1\), the adjacent threshold \(r_n^\star+1\) is also optimal. For \(n=2\), both \(r=0\) and \(r=1\) have success probability \(1/2\).
For example, with \(n=10\), the optimal threshold is \(r^\star=3\), and
\[ P_{10}(3)=\frac3{10}\left(\frac13+\frac14+\cdots+\frac19\right)\approx0.39869. \]
This exact threshold need not equal the integer obtained by simply rounding \(n/e\).
Why the 37% rule appears
Suppose \(n\) grows and \(r/n\to x\in(0,1)\). The harmonic sum satisfies
\[ \sum_{j=r}^{n-1}\frac1j =\log\left(\frac nr\right)+o(1), \]
so
\[ P_n(r)=\frac rn\sum_{j=r}^{n-1}\frac1j \longrightarrow -x\log x. \]
Differentiating yields
\[ \frac{d}{dx}[-x\log x]=-\log x-1. \]
This vanishes at \(x=e^{-1}\), where the second derivative \(-1/x\) is negative. The finite-\(n\) optimality criterion above also implies that \(r_n^\star/n\to 1/e\). Therefore,
\[ \boxed{ \frac{r_n^\star}{n}\longrightarrow\frac1e, \qquad P_n(r_n^\star)\longrightarrow\frac1e \approx 0.367879. } \]
Interpretation: for a large pool, reject about 36.8% of candidates, then accept the next record. The limiting probability of choosing the best is also about 36.8%. These are two distinct quantities that happen to share the same limit; for a fixed finite \(n\), they generally differ.
Interactive optimal threshold explorer
Explore the exact, finite-(n) probability curve for every rejection threshold. Choose (n), move the threshold (r), and compare your choice to the smallest optimal threshold. The graph uses the harmonic-sum formula—not Monte Carlo simulation.
Your exact probability
Smallest optimal threshold
Blue: exact probability · Orange: your threshold · Green: optimal threshold. For finite \(n\), ties are resolved by choosing the smallest maximizing threshold.
INTERACTIVE EXPERIMENT
Try the stopping rule
Rank 1 is the best candidate. Taller bars represent better candidates. Absolute ranks are revealed after the simulated decision for illustration; they are not available to the decision maker.
37%
Observe, then select
For large \(n\), reject approximately the first \(37\%\) of candidates and select the next record. The exact finite-\(n\) threshold comes from the harmonic-sum criterion above.
Explore further
- Backward induction: why a threshold strategy is optimal among all admissible stopping rules.
- Interactive simulations: explore stopping decisions and compare empirical success rates with exact probabilities.
- Variants and extensions: what changes when there is full information, a different target rank, or multiple selections.
- Research timeline and references: foundational work and later developments.
The classical analysis appears in Gilbert and Mosteller (1966) and the survey Freeman (1983); historical context is given by Ferguson (1989).