Optimal Stopping

In mathematics, the theory of optimal stopping or early stopping is concerned with the problem of choosing a time to take a particular action, in order to maximise an expected reward or minimise an expected cost.

Optimal stopping problems can be found in areas of statistics, economics, and mathematical finance (related to the pricing of options). A key example of an optimal stopping problem is the secretary problem. Optimal stopping problems can often be written in the form of a Bellman equation, and are therefore often solved using dynamic programming.

What does it mean?

Every decision is risky business. Selecting the best time to stop and act is crucial. When a company prepares to introduce a new saas, it must decide when to quit debugging and launch the product. When a hurricane veers toward Florida, the governor must call when it’s time to stop watching and start evacuating.

The basic framework of all these problems is the same: A decision maker observes a process evolving in time that involves some randomness. Based only on what is known, he or she must make a decision on how to maximize reward or minimize cost.

In some cases, little is known about what’s coming. In other cases, information is abundant. In either scenario, no one predicts the future with full certainty. Fortunately, the powers of probability sometimes improve the odds of making a good choice.

Historical background

The history of optimal-stopping problems, a subfield of probability theory, also begins with gambling.

One of the earliest discoveries is credited to the eminent English mathematician Arthur Cayley of the University of Cambridge. In 1875, he found an optimal stopping strategy for purchasing lottery tickets.

The wider practical applications became apparent gradually. During World War II, Abraham Wald and other mathematicians developed the field of statistical sequential analysis to aid military and industrial decision makers faced with strategic gambles involving massive amounts of men and material.

Shortly after the war, Richard Bellman, an applied mathematician, invented dynamic programming to obtain optimal strategies for many other stopping problems. In the 1970s, the theory of optimal stopping emerged as a major tool in finance when Fischer Black and Myron Scholes discovered a pioneering formula for valuing stock options.