Optimal stopping
A Socratic walk-through of optimal stopping — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #Why should you turn down the first several candidates you interview no matter how good they seem?
Suppose you are hiring, and the first candidate through the door is superb. Every instinct says take her. Yet there is advice, repeated everywhere, that says reject her — reject the first thirty-seven percent of everyone you will see, however good they are, and only then start saying yes.
Why would deliberately discarding an excellent option ever be the right move?
Reasoning it through
REASONING #The justification lives entirely in the rules of the game, so state them before anything else. You will see n candidates, one at a time, in random order. You can rank any two you have met, but you cannot score them against a standard — you only ever learn relative quality. You must accept or reject on the spot, and a rejection is final. And your payoff is all-or-nothing: getting the very best counts, and second-best counts for nothing at all.
Now ask what a decision rule can even use. At the moment a candidate arrives, all you know is whether she is the best you have seen. So a rule can only be: look at some number of candidates, refuse them all, and then take the first one who beats everyone so far. The only free parameter is where you switch from looking to leaping.
Why must there be an interior optimum? Push the switch to zero and you take the first person you meet, best with probability 1/n. Push it to the end and you almost never accept, because a late candidate rarely beats a long history. Two failure modes pulling in opposite directions guarantee a maximum between them.
Let us find it. Say you observe a fraction x of the candidates and then start accepting. You succeed if two things happen together: the overall best sits at some position t (as a fraction, beyond x), and the best of everyone before t fell inside your sample — otherwise you would have stopped earlier on someone worse. The chance the best is near t is uniform, and the chance that the best of the first t lies within the first x is exactly x/t, since order is random. Add up across all positions the winner could occupy:
P(x) = integral from x to 1 of (x/t) d*t* = x ln(1/x)
That is the whole result in one line. Differentiate: the derivative of −x ln x is −ln x − 1, which is zero when ln x = −1, that is x = 1/e = 0.3679. And the value there is (1/e) x ln(e) = 1/e again. The two famous 37 percents are the same number appearing twice, which is a coincidence of the logarithm, not a deep symmetry: the optimum sits where ln(1/x) equals 1, so the height equals the width.
Check it against the exact finite calculation rather than trusting the limit. For n = 100, computing the sum directly gives an optimum at observing 37 and accepting from the 38th onward, with a success probability of 37.1 percent. And notice how flat the top is: observing 30 gives 36.5 percent, observing 50 still gives 34.9 percent. The precise threshold barely matters; what matters enormously is that you look at some substantial prefix and then commit.
The analogy
THE ANALOGY #Think of driving a long unfamiliar road looking for the cheapest fuel, with no way to turn back and no idea what prices are normal here. For the first stretch you fill in nothing and buy nothing — you are building a price scale out of the stations you pass. Once you have a scale, the next station that undercuts everything you have seen is worth stopping for, because you finally know what "cheap" means on this road.
fuel prices come with a number attached, so a real driver could recognise an outstanding price from a single station and knows roughly what petrol costs elsewhere — whereas the whole difficulty of the stopping problem is that ranks are all you get, which is exactly the assumption that makes 37 percent the answer.
Clarifying the model
THE MODEL #The 37 percent rule is quoted far more often than its assumptions are, and each assumption carries real weight.
Random order is the load-bearing one. The derivation used "the chance the best of the first t lies in the first x is x/t", which is true only because arrival order is a uniform shuffle. If a recruitment agency sends its strongest people first, the rule is not merely suboptimal, it is close to worst possible — you would systematically discard the best and then accept a late mediocrity who happens to top a weakening field. That is the observation that would refute any real-world use of it: check whether the ordering is genuinely exchangeable before applying anything derived from this.
No recall. If rejected candidates can be recalled with some probability, the cost of looking falls and the optimal switch point moves earlier; with free recall the problem largely dissolves, since you can simply see everyone and then choose.
Ranks only. If you can observe an actual score drawn from a known distribution, the optimal rule stops being a fixed cutoff and becomes a declining threshold — demand a lot early, relax as the remaining opportunities dwindle — and it strictly beats 37 percent, because a genuinely exceptional score early on is recognisable as exceptional.
All-or-nothing payoff. This is the assumption most people implicitly reject while quoting the result. If you want a good hire rather than the single best, minimising the expected rank of your pick leads you to stop much earlier, and the limiting expected rank is a constant slightly below 4 — a figure I state from recall. "Best or bust" is a strange thing to want, and 37 percent is the answer to that strange want.
Known n. Without n there is no "37 percent of" anything; you need a known horizon or an assumption about arrivals.
One neighbourly distinction. The walk-through on completing a collection also concerns a long sequence of draws, but its pain is accumulation — how many packets to see everything — and nothing is ever forfeited. Here nothing accumulates: the whole difficulty is that rejection is irreversible, so the mathematics is about buying information with options you cannot get back.
A picture of it
THE PICTURE #How to readThe horizontal axis is how many of the hundred candidates you refuse outright before you start accepting; the vertical axis is the chance the person you finally hire is the best of the hundred. Read the curve for its shape, not its peak: it climbs steeply on the left, where you are still too ignorant to judge, crests at 37, then falls away on the right, where you have judgement but no candidates left. The plateau between roughly 25 and 50 is the practical message — the exact cutoff is nearly free to get wrong, landing far outside that band expensive.
What became clearer
WHAT CLEARED #The rule is not about caution. It is that a candidate carries two kinds of value — she might be the hire, or she might be the yardstick — and early on you cannot have both. Rejecting the first 37 percent buys the scale you need to recognise excellence, and the logarithm says that scale is worth exactly one e-fold of the field. What the folklore drops is that the answer is fragile in its assumptions and robust in its threshold: get the order random and the payoff all-or-nothing, and almost any cutoff between a quarter and a half serves nearly as well.
Where to go next
ONWARD #- The declining-threshold rule when actual values, not just ranks, are observable.
- House-selling and job-search models where each look costs money, which changes the objective entirely.
Key terms
TERMS #| Term | What it means |
|---|---|
| Secretary problem | the classical name for this setup: n candidates, random order, relative ranks only, irrevocable decisions, payoff only for the best. |
| Recall | the ability to return to a previously rejected option; assumed absent here. |
| Expected rank | an alternative objective scoring how far down the true ordering your pick fell, rather than only whether it was first. |
Every term the collection defines is gathered in the glossary.