Optimal Stopping & Thresholds
The Secretary Problem
Overview
The Secretary Problem (also: the Sultan's Dowry, the Best-Choice Problem) is the canonical optimal stopping problem WITHOUT recall. Unlike the hat problem, you cannot go back and accept a previously seen candidate. The optimal strategy is always 'skip-then-accept': observe the first k candidates for calibration, then accept the first subsequent candidate who beats all previously seen candidates. The optimal k is exactly N/e, and the success probability converges to 1/e regardless of N. This 37% rule appears constantly in finance: when to hire, when to buy an asset at an unknown price, when to accept an offer.
How to Recognize
- →Candidates/items arrive in random order, you must accept/reject immediately (no recall)
- →'Best of N' selection without being able to go back
- →You observe a ranking but not absolute values
- →'Explore then exploit' structure
- →Number of items N is known (or unknown)
Step-by-Step Approach
- 1.Observe first k candidates as 'exploration' — reject all of them
- 2.Then accept the first candidate who beats all previous (exploitation)
- 3.Optimal k = ⌊N/e⌋ ≈ 0.368N
- 4.P(selecting best) → 1/e ≈ 36.8% regardless of N (as N→∞)
- 5.For small N: compute exactly. For large N: use 1/e approximation
Key Formulas
Worked Examples
Problem
4 candidates arrive in random order. You must select exactly one, cannot recall. What is the optimal strategy and P(selecting best)?
Solution
Denote candidate quality rank as 1 (best) to 4 (worst). 4! = 24 equally likely orderings.
Strategy 'skip k, then take first record': evaluate for k=0,1,2,3.
k=0 (always take 1st): P(best) = P(rank 1 is first) = 1/4 = 25%.
k=1 (skip first, take first who beats candidate 1):
P(select best) = P(best is not 1st) × P(best comes before 2nd-best after 1st position) + ...
Direct count: out of 24 permutations, count cases where 'rank 1 is in position 2,3,4' AND 'no candidate before rank 1 (after skip) beats candidate 1 in earlier position was 2nd-best or worse'.
P = Σ_{j=2}^{4} P(best at position j) × P(best of first j-1 is in first 1 position) = Σ_{j=2}^{4} (1/4) × (1/(j-1)).
P = (1/4)[1/1 + 1/2 + 1/3] = (1/4)(11/6) = 11/24 ≈ 45.8%.
k=2: P = Σ_{j=3}^{4} (2/4)(1/(j-1)) ... P = (1/2)[1/2+1/3] = (1/2)(5/6) = 5/12 ≈ 41.7%.
k=3: P = (3/4)(1/3) = 1/4 = 25%.
Optimal k=1, P(best) = 11/24 ≈ 45.8%.
Answer
Skip 1, take first record. P(best) = 11/24 ≈ 45.8%. This beats the 1/4 = 25% from random guessing.
Common Mistakes
- !
Confusing Secretary Problem (no recall, rank-based) with the Hat Problem (i.i.d. draws with known distribution). They require different approaches.
- !
Applying the 1/e rule to problems where you DO know the distribution (can compute absolute values). The 1/e rule is for rank-only information.
- !
Forgetting the 'first record after skip' condition. You don't just pick any candidate after position k — you pick the FIRST one who beats ALL previous candidates (including the skipped ones).
- !
Using k = N/e exactly without flooring. In practice k = ⌊N/e⌋.
- !
For large N: the 1/e rule gives ~37%, not 50%. Many students think 'skip half' is optimal — it's not (gives about 25%).
Practice Problems
Click "Show Answer" to revealN=3 candidates arrive in random order. You see their quality rank (1=best, 2=middle, 3=worst). What is the optimal strategy and P(picking best)?
You're buying a car. 10 dealers offer prices (lower is better). Prices are i.i.d. from some distribution you don't know (only ranks). You can visit at most 10 dealers. Optimal strategy?