Updated
In this lesson
Wide tables, equations, and code scroll sideways. Swipe, or Tab to focus them and use the left and right arrow keys.
Secretary problem
You will learn: Choose a stopping cutoff under random order, rank-only information, and no recall.
Start with: Conditioning and independence
You are interviewing n candidates for a position, arriving in uniformly random order. After each interview you must hire or reject immediately — no going back. You want to maximise your probability of hiring the single best candidate.
The optimal strategy has a clean structure: observe and reject the first r candidates (the “scouting” phase), then hire the first candidate strictly better than all of them.
The success probability for an integer cutoff 1 ≤ r < n is (for r=0, hiring the first candidate succeeds with probability 1/n):
Open gold circle: optimal cutoff. Smaller filled blue point: your chosen cutoff.
Reveal relative ranks, one candidate at a time
The precommitted rule rejects the first 10, then selects the first new record. A smaller rank is better. Only ranks relative to candidates already revealed are shown; unseen candidates' ranks cannot guide a decision. Changing the cutoff replays a different policy on the same seeded order, not a permitted mid-interview policy change.
| Arrival | Rank among those seen | Rule decision |
|---|---|---|
| 1 | 1 of 1 | Observe and reject |
Change the rules and the optimum changes
With free recall of every candidate, wait until all arrive and choose the best: success probability one. With only two independent Uniform(0,1) values observed numerically, choose the first if it exceeds 1/2, otherwise take the second. Its success probability is 3/4, versus 1/2 with only relative ranks. These are different information sets; the 1/e rule is not a universal hiring recommendation.
The 37% rule
The demo checks every integer cutoff to find the finite-n optimum. Its large-n approximation is:
and the resulting success probability converges to:
The ochre marker identifies the best integer cutoff; the control chooses the cutoff used by the simulation and replay. Use the optimal-cutoff button to align them. The limiting 1/e fraction is an approximation, not an exact small-n rule.
What to notice
- An early cutoff sacrifices information. With r=0 you hire the first candidate, who has probability 1/n of being the best.
- Too late and you miss the best. With a large cutoff, the best candidate often appears in the scouting phase and you never hire them.
- Compare exact cutoffs. The losses on either side of the optimum depend on n and how far the cutoff moves.
- The rule is n-independent in the limit. The 37% fraction is an asymptotic guide; for small n, compare the exact integer cutoffs.
Real applications
The secretary problem formalises one specific optimal-stopping model: a known number of candidates, random order, only relative ranks observed, no recall, and an objective of selecting the single best. Real decisions may violate these assumptions. Other optimal-stopping models arise in:
- Choosing when to sell a house (after seeing enough offers to set a benchmark)
- Deciding when to commit in a relationship
- Algorithm design (online algorithms that must make irrevocable decisions with incomplete information)
Derive the success probability
Suppose the best candidate arrives at position j > r. The rule selects that candidate exactly when the best of the first j−1 candidates was in the initial r, so that no earlier post-cutoff record caused a hire. Under a uniformly random permutation that chance is r/(j−1). Each arrival position of the overall best has probability 1/n. Summing over j=r+1,…,n produces the displayed formula.
At n=5, the success probabilities for r=0,1,2,3,4 are 1/5, 5/12, 13/30, 7/20, and 1/5. Rejecting two is optimal, with success 13/30 ≈ 43.3333%, not 36.8%. For large n and cutoff fraction x, the sum approaches −x log x; differentiating gives the maximum at x=1/e.
Make a prediction
If the overall best candidate was in the rejected prefix, can the cutoff rule still succeed?
Explore the answer
No. With no recall, that candidate is gone. If no later record appears, the demo reports no selection. Forcing a last-candidate selection in that case would not recover the rejected best and therefore would not change the success probability.
Observe only the available information
Before the full reveal, the table reports each candidate’s rank among arrivals so far. The first candidate is always “1 of 1”; that gives no evidence that they are the overall best. Absolute ranks appear only after the full order is revealed. The rule’s decision uses the prefix, never a later candidate’s value.
A cutoff must be chosen before using the revealed order to assess its performance. Adjusting it after seeing the order is useful for comparison, but is not the same online policy as committing to that cutoff in advance. A lucky success on one sequence does not prove that the cutoff maximizes repeated success.
Change the information or objective
With free recall, observing everyone and choosing the best succeeds with probability one. The irrevocable decision constraint is doing real work.
For a two-candidate example with observed numerical values independently Uniform(0,1), the optimal rule chooses the first value x if x ≥ 1/2; otherwise it waits for the second. If you take x, your chance of beating the unseen second is x; if you wait, it is 1−x. Averaging max(x,1−x) over a uniform first value gives 3/4. With only relative ranks and two candidates, the best success probability is 1/2. Numerical values and a known distribution provide information missing from the classical model.
Make a prediction
Does maximizing the probability of selecting the very best also necessarily maximize the expected selected value?
Explore the answer
No. Those are distinct objectives. Rank-only success assigns the same failure value to every non-best candidate, whereas an expected-value objective distinguishes how good those alternatives are and requires more model information.
References
Random Services: the secretary problem states the classical assumptions and derives its finite-cutoff probability. Ferguson’s Optimal Stopping and Applications places rank and full-information variants in a broader framework. The two-uniform example above is a direct one-step comparison, not a claimed solution to all full-information stopping problems.