Look, Then Leap

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. The classical record and best-choice figures are recomputed in your browser using the same formulas as the offline verifier.

I · The records hiding in any list

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 H_n = 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."

II · Play it yourself

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?

III · Look, then leap

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) ), for r ≥ 2.
For r = 1, P(win) = 1/n.

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.

IV · Why 1/e, twice

The win formula has a clean reading. For r ≥ 2, suppose the true best arrives at position j ≥ r. That position has probability 1/n. Given that, you reach it without an early, wrong leap exactly when the best of the first j−1 candidates was among the r−1 rejected ones, with probability (r−1)/(j−1). Sum those products over j = r, …, n, then factor out (r−1)/n to get the displayed formula. Maximizing it gives a strikingly tidy stopping rule: choose the least r with 1/r + … + 1/(n−1) ≤ 1, then take the first record at or after r. This stopping-rule tail starts one term later than the tail in the win formula.

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.

V · The honest edges

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 adversarial order removes the classical constant success guarantee; a uniformly random choice still wins with probability 1/n under any fixed order.
· 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, with values drawn independently from a known continuous distribution, the "full-information" game has an optimal win probability tending to about 58% as n grows (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; for its limiting expected rank, a reported numerical lower bound is about 1.908, and Meier & Sögner give a strategy with expected rank about 2.32614. 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.

Sources

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; an early journal solution.
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, with the classical secretary problem as a special case.
Meier, M. & Sögner, L. A new strategy for Robbins’ problem of optimal stopping, arXiv:1606.03348; limiting expected-rank bounds: the numerical upper value ≈ 2.32614, and the reported lower bound ≈ 1.908 credited to Bruss & Ferguson (1993).