Matpic
mathematics, in pictures
Concept

Optimal stopping

Choosing when to accept an offer that arrives in a sequence, with no going back. What the answer looks like depends entirely on what the chooser is told and what counts as success, and changing either produces a different constant from the same arrival process.

Named by 6 essays across one field — each of them below, with the objects they name alongside it.

Also named here as threshold rule — the same set of essays touches all of them, so they are one junction rather than several.

5,040 orders, 7 thresholds, one best rule. For each number of candidates passed over, the share of the 5,040 possible arrival orders in which the rule ends up with the best of the 7. The count is exhaustive.

When to stop looking

Candidates arrive one at a time in a random order. Each must be accepted or rejected on the spot, with no going back and no way to know what is still to come. The best possible rule is to look at about a third of them and then take the first one that beats everything seen — and it works about a third of the time, however many there are.

probability · Optimal stopping 58.6% at 46 candidates, against 37% without the values. The chance of ending with the best candidate when the values are shown, against the number of candidates, for 10 sizes. It falls towards 0.5802 rather than towards 1/e.

When the numbers are shown

The secretary rule wins a third of the time and cannot do better, because it is told only who is ahead. Show the actual values and say where they came from, and the same problem is won three times in five — by a standard that falls as the end approaches.

probability · Optimal stopping About the fourth-best, whatever the size of the field. The smallest expected rank achievable by an online rule, against the number of candidates, for 10 sizes. It rises to 3.8516 at 2500 candidates and its limit is 3.8695.

Giving up on the best

The secretary rule treats landing the second-best exactly as badly as landing the worst, which is a strange thing to want. Ask instead for the smallest average rank and the answer is about the fourth-best candidate — whatever the size of the field, and whether it is ten or ten million.

probability · Optimal stopping An online rule taking nine tenths of what an oracle takes. The share of the oracle's expected maximum secured by the best single threshold, and by the threshold at the median of the maximum, for 8 field sizes of independent uniform values.

Half of what an oracle takes

Compare an online rule not against the best it could have done but against a rule that has seen every value in advance. One fixed threshold secures half of what the oracle collects, whatever the distributions are — and there is an example on which half is all there is.

probability · Optimal stopping Up to 4 choices among 60, and the thresholds that nest. For 60 candidates in random order and 1, 2, 3, 4 acceptances, the chance of ending with the best among those accepted — 37.3%, 60.0%, 74.3%, 83.5% — and where along the sequence the rule starts accepting for each number of choices in hand.

The thresholds that nest

Allow a second acceptance in the secretary problem and the chance of holding the best rises from about 37 per cent to about 59. The best rule is still a threshold — but one threshold for each number of choices still in hand, the earlier ones starting sooner, and each additional choice buying less than the one before.

probability · Optimal stopping Add the odds from the end: start at event 5 of 12. The odds of 12 independent events with chances 1/k — the secretary problem, the sum of the odds from the end reaching one at event 5, and the chance of stopping on the last success from each starting point, highest at 39.6%.

Add the odds from the end

Watch a sequence of independent events and try to stop exactly on the last one that happens. Add up the odds of the events from the end backwards until the total reaches one, and stop at the first success from there. That rule is the best possible for any probabilities whatever, and the secretary problem is the special case in which the chances are one over the position.

probability · Optimal stopping

Named alongside it

The objects these essays reach for when they reach for this one.

Threshold ruleConditional probabilityIrrevocable decisionBackward inductionDecision proceduree, the numberExpectationCounting argumentHarmonic seriesPermutationBoundCompetitive ratio

All concepts