You meet n strangers one at a time, in a random order, and must pick the single best — accepting or rejecting each on the spot, forever. How? And how often can you possibly win?
The rule is cruel in its simplicity. The candidates arrive one by one. You can compare whoever is in front of you to everyone you've already seen — but the moment you reject someone they're gone, and the moment you accept someone you stop. No going back. You want the very best of all n; second-best is a loss like any other. It feels hopeless: the best might be first, and you'd never know to keep them; or last, and you'd have leapt too soon.
It is not hopeless. There is a strategy that wins astonishingly often — close to 37% of the time, no matter how large n is — and finding it begins not with the choosing at all, but with a quiet fact about any random list. Every number on this page is recomputed in your browser by the same routine the offline verifier runs.
Forget choosing for a moment. Just walk down a shuffled list of distinct things and call out each one that is the best you've seen so far — a new high-water mark. Statisticians call these records, or left-to-right maxima. The first item is always a record. After that they get rarer.
Here is the fact the whole problem rests on. In a uniformly random order, the probability that the item in position k is a record is exactly 1/k — and it depends on nothing else. Not the distribution the numbers came from, not their spread, not n. The reason is almost too short to be a proof: among the first k items, each is equally likely to be the largest, so the last of them is largest with probability 1/k.
Two consequences matter for what follows. First, the expected number of records in a list of n is Hn = 1 + ½ + ⅓ + … + 1/n, which grows like ln n + γ (γ ≈ 0.5772, the Euler–Mascheroni constant) — agonizingly slowly. Second, and stranger: the record-or-not coin flips at the different positions are mutually independent. Whether position 3 broke the record tells you nothing about whether position 9 will. The verifier checks both facts exactly, by literally enumerating every permutation for small n.
Now bring choosing back. You can only ever accept a record — accepting a non-record means knowingly taking someone you've already seen beaten, which can never be the overall best. So your job reduces to: which record do I leap at? Early records are common but probably not the global best; late records are rare but, if they come, are likely the real thing. The art is the threshold between "too early to trust" and "now."
Before the answer, try to feel the trap. Below, 25 applicants arrive in random order. You see each one's rank so far — "best yet", or "3rd best of the 7 seen" — never the true rank, because in real life you can't. Hire to stop and take the one in front of you; pass to send them away forever. Did you land the single best of all 25?
The best possible strategy has a shape so plain it sounds like folk advice: look, then leap. Reject the first r − 1 candidates no matter how dazzling — these are pure reconnaissance, used only to learn how good "good" is. Remember the best among them. Then leap at the very first later candidate who beats that benchmark. (If none does, you're stuck with the last — a loss.)
Everything hinges on the cutoff r. Look too briefly and you leap at an early record that isn't the real best; look too long and the true best is probably already behind you, spent in reconnaissance. There is a sweet spot, and because we know the exact win probability for every cutoff, we can simply find its peak:
P(win | cutoff r) = (r−1)/n · ( 1/(r−1) + 1/r + … + 1/(n−1) )
Drag the cutoff and watch the win curve. The peak is the optimal place to stop looking — and the page marks where 1/e falls.
The win formula has a clean reading. The factor (r−1)/n is the chance the true best falls after your reconnaissance phase — necessary, or you've already thrown it away. The sum 1/(r−1) + … + 1/(n−1) is, position by position, the chance that the best of everything-so-far sat safely inside the reconnaissance and so didn't trigger an early, wrong leap. Maximizing their product gives a strikingly tidy stopping rule: keep looking exactly while that tail sum is still above 1, and leap once it drops to 1 or below.
For large n the tail sum 1/(r−1) + … + 1/(n−1) is close to ln(n/r), so the rule becomes ln(n/r) = 1 — that is, r = n/e. Substitute that cutoff back and the win probability collapses to 1/e as well. So the same constant governs how long to look (a fraction 1/e of the line) and how often you win (a probability 1/e). It is the harmonic-sum-becomes-logarithm of §I, surfacing twice in one answer.
The headline is genuinely surprising in both directions. That you should reject the first third or so outright is counterintuitive; that doing so wins more than a third of the time — when blind guessing wins 1/n, vanishing toward zero — is the part people refuse to believe. With a hundred candidates the look-then-leap rule beats pure chance by a factor of 37, and the advantage only widens with n.
This clean answer is paid for by four assumptions, and it's worth saying exactly which, because real decisions usually break at least one:
· You know n. The count of candidates is fixed and known in advance. (If candidates arrive over an unknown horizon, the problem changes and so does the rule.)
· Random order. The arrival order is a uniformly random shuffle — the engine that makes "1/k" true. An adversary who orders the candidates can defeat any strategy.
· No recall. A rejected candidate is gone for good. Allow recalls and you can do better.
· All-or-nothing. Only the single best counts; second-best scores zero.
That last assumption is the sharpest. If instead you want the best expected rank — to usually land someone very good, not necessarily #1 — the optimal rule is different and the achievable limit is a different constant, about 3.8695 (the expected rank you can guarantee as n→∞; Chow, Moriguti, Robbins & Samuels, 1964). And if you can see each candidate's actual value, not just their rank-so-far — the "full-information" game — you can win about 58% of the time (Gilbert & Mosteller, 1966), far better than 1/e. The closely related question of minimizing expected rank with full information, called Robbins' problem, is still unsolved — its limiting value is only known to lie between about 1.908 and 2.329. These numbers are cited from the literature, named here, not derived on this page; the page derives and checks only the classical best-choice result.
What is exact and machine-checked: the 1/k record law and the harmonic expectation (by full enumeration), the win formula for every cutoff (closed form versus brute force over all n! orders), the exact small-n optima, the tail-sum stopping rule, and both 1/e limits — plus an independent Monte-Carlo run of the rule itself. The figures below recompute live above.
Gardner, M. (1960). Mathematical Games. Scientific American 202(2) & (3) — the "game of googol," which popularised the problem.
Lindley, D. V. (1961). Dynamic programming and decision theory. Applied Statistics 10:39–51 — the first solution in print.
Dynkin, E. B. (1963). The optimum choice of the instant for stopping a Markov process. Soviet Math. Dokl. 4 — the optimal-stopping framing.
Chow, Y. S., Moriguti, S., Robbins, H. & Samuels, S. M. (1964). Optimal selection based on relative rank. Israel J. Math. 2:81–90 — the expected-rank problem; the limiting constant ≈ 3.8695.
Gilbert, J. P. & Mosteller, F. (1966). Recognizing the maximum of a sequence. J. Amer. Stat. Assoc. 61:35–73 — the full-information game (≈ 0.58).
Rényi, A. (1962). Théorie des éléments saillants d'une suite d'observations. — the theory of records; P(record at k) = 1/k and their independence.
Ferguson, T. S. (1989). Who solved the secretary problem? Statistical Science 4(3):282–296 — the history, and a caution about what "solved" means.
Bruss, F. T. (2000). Sum the odds to one and stop. Annals of Probability 28:1384–1391 — the odds theorem, of which the 1/e rule is the special case; and the bounds on Robbins' problem.