FEATURE ARTICLE
Knowing When to Stop
How to gamble if you must—the mathematics of optimal stopping
Theodore Hill
Unsolved Problems
Although many stopping problems have been solved, there are still tantalizingly simple unsolved problems, even ones involving full information. My favorite is this: Toss a fair coin repeatedly and stop whenever you want, receiving as a reward the average number of heads accrued at the time you stop. If your first toss is a head, and you stop, your reward is 1 Krugerrand. Since you can never have more than 100 percent heads, it is clearly optimal to stop in that case. If the first toss is a tail, on the other hand, it is clearly best not to stop, since your reward would be zero. Suppose the first toss is a tail and the second a head. You may quit then and receive half a Krugerrand, or continue to toss. A moment’s reflection shows that it is never optimal to stop with half a Krugerrand or less, since the law of large numbers says that the average number of heads will converge over time to 50 percent, and in doing so will oscillate above and below 50 percent repeatedly. Stopping with 50 percent or less is simply not greedy enough.
With a little more difficulty it can be shown that stopping with the third toss if you saw tailheadhead is optimal, and that stopping the very first time you observe more heads than tails is optimal for a while. But stopping the first time you have one more head than tails is not optimal forever. After a certain critical time you should only stop when you have two more heads than tails, and after a second critical time, stop only when you are three heads ahead, and so forth. The proof of this fact, which relies on the law of the iterated logarithm, is not easy, and the complete list of critical times is still not known. Backward induction will not work for this problem since there is no
a priori
end to the sequence and, hence, no future time to calculate backwards from. Even though Wolfgang Stadje of the University of Osnabrük has advanced this problem very recently, and despite the gains of a century of development of mathematical probability, the exact optimal rule for all sequences of heads and tails is unknown.
Still, the general field of optimal stopping, especially with its applications to financial markets, continues to develop at a rapid pace. In fact, some experts feel that the pace has been too quick and that computer models of option and derivative pricing (basic optimalstopping problems) are the roots of the current economic crisis. But it is not the theory that is at fault. Like Steven Shreve of Carnegie Mellon University, I blame the decision makers’ blind trust in computer model predictions. In fact, new ideas and discoveries in optimal stopping, including better estimates of the risk that mathematical models are wrong, are exactly what we need?not only for guidance on when to stop the bailouts, for example, but also for help with multiple other monumental problems, including when to stop using fossil fuels or stockpiling nuclear weapons.
Bibliography

Boshuizen, F., and T. Hill. 1992. Momentbased minimax stopping functions for sequences of random variables.
Stochastic Processes and Applications
43:303316.

Bruss, F. T. 2000. Sum the odds to one and stop.
Annals of Probability
28:13841391.

Chow, Y., H. Robbins and D. Siegmund. 1991.
Great Expectations: The Theory of Optimal Stopping
. Mineola, N.Y.:
Dover Publications.

Cover, T. 1987. Pick the largest number, in
Open Problems in Communication and Computation
, eds. Cover, T., and B. Gopinath. New York: SpringerVerlag, p. 152.

Dubins, L., and L. Savage. 1976.
Inequalities for Stochastic Processes: How to Gamble If You Must.
New York: Dover Publications.

Ferguson, T. 1989. Who solved the secretary problem?
Statistical Science
4:282296.

Freeman, P. R. 1983. The secretary problem and its extensions: A review.
International Statistical Review
51:189208.

Hill, T., and U. Krengel. 1992. Minimaxoptimal stop rules and distributions in marriage problems.
Annals of Probability
19:342353.

Hill, T., and D. Kennedy. 1992. Sharp inequalities for optimal stopping with rewards based on ranks.
Annals of Applied Probability
2:503517.

Jacka, S.,
et al
. 2007. Optimal stopping with applications.
Stochastics 79:
14.

Peskir, G., and Albert Shiryaev. 2006.
Optimal Stopping and Free Boundary Problems
. Boston: Birkhäuser.

Samet, D., I. Samet and D. Schmeidler. 2004. One observation behind twoenvelope problems.
American Mathematical Monthly
111:347351.

Shreve, S. 2008. Don’t blame the quants.
Forbes.com. http://www.forbes.com/2008/10/07/securitiesquantsmodelsopedcx_ss_1008shreve.html

Stadje, W. 2008. The maximum average gain in a sequence of Bernoulli trials.
American Mathematical Monthly
115:902910.