Matpic
mathematics, in pictures
Concept

Backward induction

Solving a sequential decision by starting at the end, where the answer is forced, and working towards the present. Each step compares acting now against a value already computed for everything later, which is what makes the calculation finite rather than a search over strategies.

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

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

Named alongside it

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

Conditional probabilityDecision procedureExpectationIrrevocable decisionOptimal stoppingThreshold ruleCounting argumente, the number

All concepts