FEATURE ARTICLE

# Knowing When to Stop

How to gamble if you must—the mathematics of optimal stopping

Every decision is risky business. Selecting the best time to stop and act is crucial. When Microsoft prepares to introduce Word 2020, 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. Bad timing can be ruinous. Napoleon learned that the hard way after invading Russia. We face smaller-consequence stopping decisions all the time, when hunting for a better parking space, responding to a job offer or scheduling retirement.

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.

While much of mathematics has roots that reach back millennia to Euclid and even earlier thinkers, the history of probability is far shorter. And its lineage is, well, a lot less refined. Girolamo Cardano’s famed 1564 manuscript
*
De Ludo Aleae*, one of the earliest writings on probability and not published until a century after he wrote it, primarily analyzed dice games. Although Galileo and other 17th-century scientists contributed to this enterprise, many credit the mathematical foundations of probability to an exchange of letters in 1654 between two famous French mathematicians, Blaise Pascal and Pierre de Fermat. They too were concerned with odds and dice throws—for example, whether it is wise to bet even money that a pair of sixes will occur in 24 rolls of two fair dice. Some insisted it was, but the true probability of a double six in 24 rolls is about 49.1 percent.

That correspondence inspired significant advances by Abraham de Moivre, Christiaan Huygens, Siméon Poisson, Jacob Bernoulli, Pierre-Simon Laplace and Karl Friedrich Gauss into the 19th century. Still, for a long time there was no formal definition of probability precise enough for use in mathematics or robust enough to handle increasing evidence of random phenomena in science. Not until 1933, nearly four centuries after Cardano, did the Russian mathematician Andrey Kolmogorov put probability theory on a formal axiomatic basis, using the emerging field we now call measure theory.

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. That transformed the world’s financial markets and won Scholes and colleague Robert Merton the 1997 Nobel Prize in Economics. (Black had died by then.)

The Black-Scholes formula is still the key to modern option pricing, and the optimal-stopping tools underlying it remain a vigorous area of research in academia and industry. But even elementary tools in the theory of optimal stopping offer powerful, practical and sometimes surprising solutions.

**IN THIS SECTION**

EMAIL TO A FRIEND :

# Comments

This is a classic! It is a masterpiece in
exposition.
BTW, in the Chow-Robbins coin-tossing game, the statement that tail-head-head is a STOP is in error. It is a GO!
(if you expect to live long enoug...

posted by Doron Zeilberger

July 10, 2009 @ 8:52 AM

**Of Possible Interest**

**Essay**: Invitation to an Insect Rendezvous

**Feature Article**: Twisted Math and Beautiful Geometry

**Spotlight**: First Person: Exploring the Unconscious Brain

**Other Related Links**

Optimal stopping and applications

Best choice problems (Visual Wikipedia)