Logo IMG
HOME > PAST ISSUE > March-April 2009 > Article Detail


Knowing When to Stop

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

Theodore Hill

N = 2 Surprise

Now, suppose you must decide when to stop and choose between only two slips of paper or two cards. You turn one over, observe a number there and then must judge whether it is larger than the hidden number on the second. The surprising claim, originating with David Blackwell of the University of California, Berkeley, is that you can win at this game more than half the time. Obviously you can win exactly half the time by always stopping with the first number, or always stopping with the second, without even peeking. But to win more than half the time, you must find a way to use information from the first number to decide whether or not to stop. (Readers take comfort: When mathematicians first heard this claim, many of us found it implausible.)

Here is one stopping rule that guarantees winning more than half the time. First, generate a random number R according to a standard Gaussian (bell-shaped) curve by using a computer or other device. Then turn over one of the slips of paper and observe its number. If R is larger than the observed number, continue and turn over the second card. If R is smaller, quit with the number observed on the first card. How can such a simple-minded strategy guarantee a win more than half the time?

Figure%204.%20Stopping%20strategy%20using%20Gaussian%20random%20number%20generatorClick to Enlarge Image If R is smaller than each of the two written numbers, then you win exactly half the time ( p / 2 of the unknown probability p in Figure 4); if it is larger than both, you again win half that time ( q / 2 of q, also in Figure 4). But if R falls between the two written numbers, which it must do with strictly positive probability (since the two numbers are different and the Gaussian distribution assigns positive probability to every interval) then you win all the time. This gives you the edge you need, since p / 2 + q / 2 + 1–p–q is greater than ½, because 1 - p - q is greater than zero. For example, if the two hidden numbers are 1 and π, this Gaussian method yields a value for p about .8413 and q about .0008, so the probability that it will select the larger number is more than 57 percent.

Of course if the number writer knows this Gaussian strategy, he can make your winnings as close to ½ as he wants by writing numbers that are very close.

If the number writer is not completely free to pick any number, but instead is required to choose an integer in the range {1,2,…,100}, say, then he cannot make your probability of winning arbitrarily close to ½. In this case it also seems obvious that the number-writer would never write a 1, since if you turn over a 1, you will always win by not stopping. But if he never writes a 1, he then would never write a 2 either since he never wrote a 1, and so on ad absurdum . Interested readers are invited to discover for themselves the optimal strategy in this case, and the amount more than ½ one can guarantee to win on the average.

comments powered by Disqus


Subscribe to American Scientist