When to stop looking

A fixed number of candidates will be seen, one at a time, in an order nobody controls. Each can be ranked against the ones already seen and against nothing else. After each, a decision has to be made immediately: accept and the process stops, reject and that candidate is gone.

The goal is to end up with the best of them all. Not a good one — the best, with nothing else counting as success.

Taking the first candidate wins one time in seven, since the best is equally likely to arrive at any position. Taking the last wins one time in seven for the same reason. In between there is a rule that wins more than a third of the time, and the figure finds it by trying every rule against every order.

The rule worth considering #

A rule for this problem is a strategy: at each arrival, a decision that may depend on everything seen so far. That is an enormous space of possible strategies, and the first useful observation cuts it down to almost nothing.

The only thing worth knowing about a candidate is whether it is the best so far. Its exact rank among those seen is irrelevant, because a candidate that is not the best so far cannot possibly be the best overall, and accepting it would be a guaranteed loss. So a sensible rule only ever accepts a candidate that leads the field, and the only remaining question is when it becomes willing to do so.

That reduces the strategy space to rules of one shape: pass over the first r candidates whatever they are, then accept the first one that beats all of those. There are n such rules for n candidates, and one of them is optimal — a fact that needs proof and that the enumeration above sidesteps by simply trying all of them.

Counting the orders #

The figure counts by brute force. Every one of the 5,040 orders of seven candidates is generated, and for each order and each threshold the rule is run to see whether it lands on the best. That is 5,040 orders times 7 thresholds, and the answer is a count of orders rather than a probability estimated by sampling.

There is a formula, and it is derived by asking when a threshold rule succeeds. Fix the threshold r. The rule wins exactly when the best candidate arrives at some position i after r, and the best of the first i − 1 candidates arrived in the first r. The first event has probability 1/n; the second, given the first, has probability r/(i − 1), since the leader of the first i − 1 is equally likely to be any of them. Summing over the positions i gives

$$P(r) = \frac{r}{n}\sum_{i=r+1}^{n}\frac{1}{i-1}.$$

That is a sum of reciprocals, which is to say a piece of the harmonic series, and it is the reason a logarithm appears in the answer.

The figure computes both — the count over every order, and the formula — and requires them to agree to twelve decimal places for every threshold. Neither is trusted on its own: the enumeration could be running the rule wrongly and the formula could be derived wrongly, and the two are wrong in different ways or not at all.

Where the third comes from #

Write r = xn and let n grow. The sum of reciprocals from xn to n is approximately the natural logarithm of 1/x, so the success probability approaches x ln(1/x).

Maximising x ln(1/x) is a one-line calculus problem whose answer is x = 1/e, and the value there is also 1/e. So both the best share to pass over and the resulting chance of success converge to the same number, about 0.3679.

The figure finds that maximum by searching twenty thousand values of x rather than by differentiating, and then checks that the location and the height agree with 1/e to four decimal places. Two appearances of the same constant, from a problem with no exponentials anywhere in its statement.

Why 1/e appears at all is worth a sentence, because it is not a coincidence and it is not deep either. The quantity being maximised is a share multiplied by a logarithm of that share, the logarithm’s derivative introduces a reciprocal, and setting the result to zero produces an equation whose solution is a logarithm equal to one. Wherever a rate equals a quantity, e turns up, and this is that situation dressed as a decision problem.

The logarithm was there from the start #

The formula’s inner sum is a run of reciprocals, and that is not a detail of the derivation but the source of the whole answer’s shape.

Adding 1/r + 1/(r+1) + … + 1/(n−1) is, to within a vanishing correction, ln(n/r). So the success probability is a share multiplied by the logarithm of one over that share, and everything that follows — the optimum at 1/e, the equality of the best share and the best chance — is a fact about the function x ln(1/x) rather than about candidates.

The harmonic series turning up in a counting problem is a recurring event on this site, and the reason is always the same: a sum over positions where the kth position contributes 1/k. Here that weight is the chance that the leader among the first k is in a particular part of the list. In the coupon-collector count it is the expected wait for the next new item. The same series, and two problems that share nothing else.

What the rule is not #

Three misreadings are common enough to be worth heading off, and each is a case of the objective being different from the one people assume.

It does not maximise the expected rank. The rule is built to hit the single best candidate and treats every other outcome as an equal failure — landing the second-best counts exactly as badly as landing the worst. If the objective is instead to get a good candidate on average, the optimal rule is a different one, it accepts much sooner, and it achieves an expected rank of about 3.87 however many candidates there are, which is a far more useful guarantee and a much less famous result.

It does not assume anything is known about quality. No distribution of candidate quality is used anywhere. Only the relative ranking of what has been seen matters, so the answer is the same whether the candidates are scored out of ten or out of a million. That is what makes the result robust, and also what makes it weak: a rule allowed to use the actual numbers can do considerably better.

One third is not a high chance. Succeeding 37% of the time is optimal and it is still failure most of the time. What the theorem says is that no rule does better, not that this rule does well — and the gap between those two statements is where the practical value of the result lives.

The third of these is the one that turns the result from a curiosity into a piece of decision theory, and it is worth putting beside the other rules-for-choosing on this site. A voting rule is judged by which properties it satisfies and every rule fails some of them; a stopping rule is judged by a probability and the best one fails most of the time. In both cases the mathematics does not deliver a satisfactory answer, it delivers a ceiling — and knowing the ceiling changes what counts as a reasonable complaint about the outcome.

What it costs #

Enumerating every order costs n factorial, which is 40,320 at eight candidates and about two million at ten. The figures stop at eight for that reason, and the honest description of the choice is that eight is where an exhaustive check is still cheap enough to be redone every time the picture is drawn.

The formula costs a sum of n reciprocals for each threshold, so finding the best threshold by trying all of them costs about n² operations — trivial at any size. The asymptotic answer costs nothing at all: pass over the first 37% and take the next leader.

The interesting cost is elsewhere. Deciding that threshold rules are optimal — that no cleverer strategy using more information can beat the best of them — is a genuine argument by backward induction, working from the last candidate to the first and showing at each step that the decision depends only on whether the current candidate leads and how many remain. The enumeration here does not establish that. It finds the best rule of that shape, and the claim that the shape is not a restriction comes from elsewhere.

Where it appears with the numbers changed #

Irrevocable decisions under uncertainty are a large subject, and this problem is its cleanest instance rather than an isolated puzzle.

The same structure appears whenever offers arrive over time and cannot be recalled: house-hunting with a deadline, choosing when to sell an asset that will be offered a fixed number of times, deciding when to stop testing candidates in an experiment. The mathematics changes with the objective and with what is known, and the shape of the answer — a period of pure observation followed by a threshold — survives a great deal of that variation.

The contrast with stable matching is worth drawing. There, decisions are also made in sequence and offers are also rejected, but a rejected proposer may try again and an accepted one may be dropped later, so the process can converge on an outcome nobody wants to leave. Here nothing can be revisited, and the price of that is that no rule can guarantee anything at all — only a probability.

The other place the same constant shows up #

There is a second question about permutations on this site whose answer is 1/e, and the two have nothing to do with each other.

The chance that a shuffle leaves nothing in place tends to 1/e as well, and the coincidence is worth examining rather than admiring. There, the constant comes from an alternating sum — the inclusion–exclusion count of arrangements avoiding every fixed point, whose terms are the reciprocals of factorials, which is the series for e⁻¹. Here it comes from maximising a logarithm. Two different series, two different arguments, one number.

That is what a constant being fundamental means in practice. It is not that the two problems are secretly the same; it is that e is what the exponential function is built from, and any process whose structure involves multiplying a great many small independent factors, or whose optimum involves a rate equalling a level, will produce it. The two problems here are instances of the second and the first respectively.

The pair is also a caution. Seeing 0.3679 in the answer to a new counting problem is weak evidence that it is related to either of these, and the temptation to look for a common mechanism should be resisted until one is found.

What the picture cannot show #

The bars count orders, and an order is a permutation, so every figure here is about a finite list of possibilities. The limit — the 1/e that the whole result is remembered for — is not in any of them, and the dots on the curve figure stop at eight because the enumeration does.

Nothing in the pictures establishes that threshold rules are the best kind of rule. That claim is the one piece of the argument with no drawing attached, and it is the piece a sceptical reader should ask about first.

And the figures show success rates, not what happens on failure. A rule that fails might end with the second-best candidate or with the worst, and the pictures treat those identically because the problem does. A reader wanting to know how bad the failures are is asking a question this formulation cannot answer.

The ladder from here #

Rungs above: the backward-induction proof that threshold rules are optimal. The full-information version, where candidate values are drawn from a known distribution and the optimal rule uses thresholds that fall over time. The expected-rank objective and its constant 3.87. The problem with a random number of candidates, where the answer changes shape. The multiple-choice version, where several candidates may be accepted. Prophet inequalities, which compare an online rule against an oracle that sees everything in advance and guarantee half the oracle’s value. And the connection to optimal stopping in continuous time, where the same question is asked of a process that never stops arriving.

The shape of the idea #

Two things make this problem worth its reputation, and neither is the constant.

The first is the reduction. An enormous space of possible strategies collapses to n rules on the single observation that a candidate not currently leading is worthless. That step is a rewriting rather than a calculation, and it is the reason the problem is solvable at all — everything afterwards is arithmetic on a list of n numbers.

The second is that the answer is a limit that does not depend on the size of the problem. Whether there are a hundred candidates or a million, the advice is the same: watch 37%, then take the next leader, and expect to succeed 37% of the time. A rule whose form and whose performance are both independent of the scale is rare, and it is what makes a piece of mathematics quotable outside its own subject.

The habit worth taking away is the one the figures embody: a formula was derived and an exhaustive count was run, and the two were required to agree before either was believed. The derivation is short enough that its errors are hard to see, and forty thousand orders is small enough that a computer can check it exactly.