Backward induction
Named by 7 essays across 2 fields — each of them below, with the objects they name alongside it.
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.
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.
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.
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.
The player who meets the first long run
Turn Euclid's algorithm into a game: two players take turns cutting squares off the rectangle, any number from the current run, and whoever cuts the last one wins. The whole game is decided before it starts — by whether the ratio of the sides is more or less than the golden ratio, which is the same thing as how many runs of length one come first.
![What a rule collects when every value comes from the same distribution. uniform on [0, 1]: best rule 0.995, one threshold 0.635 of E[max] at n = 200; exponential: best rule 0.905, one threshold 0.678 of E[max] at n = 200; Pareto, tail exponent 2: best rule 0.802, one threshold 0.714 of E[max] at n = 200; Pareto, tail exponent 1.2: best rule 0.802, one threshold 0.682 of E[max] at n = 200.](/f/what-a-rule-collects-when-every-value-comes-from-the-same-distribution-cdb6768b.svg)
When every value comes from the same hat
A rule that sees values one at a time and must keep or discard each on the spot can guarantee half of what a prophet collects, and no more, when the values come from different distributions. When they all come from the same one, the guarantee rises to 0.745 — and a single fixed threshold, set so that each value crosses it with chance 1/n, already secures 1 − 1/e. For bounded values the best rule collects nearly everything; only a heavy tail, where one enormous value carries the prize, keeps the gap open.
The rank that remembers every value
Values arrive one at a time, each must be kept or discarded on the spot, and the aim is to keep one whose rank among all of them is low on average. Told only who is leading, the best rule gets 3.87. Shown the values, a rule gets below 2.33 — and how much lower the best possible rule goes is not known, because the rank of what is kept depends on every value seen, and the best rule may need to remember all of them.
Named alongside it
The objects these essays reach for when they reach for this one.
Optimal stoppingThreshold ruleIrrevocable decisione, the numberExpectationConditional probabilityDecision procedureContinued fractionsCounting argumentEuclidean algorithmExhaustive searchFibonacci