scvalex.net

28. A Stopping Problem

Let’s play the following game: you roll a four-sided die; if 1 or 2 come up, you get 1$; if 3 comes up, you lose 1$; if 4 comes up, the game ends, and you lose all of your gains; finally, you can stop the game at any point and keep your gains. How do you play so that you maximize your gains?

For practice, let’s find a strategy for a simpler game: the rules are the same, except that if 4 comes up, the game ends, but you don’t lose any gains. The rules are easier to reason about now: for any one round, there’s a 25% chance of losing 1$, a 50% chance of gaining 1$, and a 25% chance of the game ending. In other words, for any one round, you have an expected gain of \(25\% \times (-1\$) + 50\% \times 1\$ = 0.25\$\). So, a good strategy would simply be to play for as long as possible.

Back to our problem: it’s the same as above, but getting a 4 means losing everything. So, in order to make a profit, we must stop voluntarily. Since we still make an expected 0.25$ on each round, we still want to play for as long as possible. The probabilities of not getting a 4 tell us how long we can keep going: we get to the second round in \(3/4\) of the cases, to the third in \((3/4)^2\) of the cases, and so on.

Round Probability of reaching round
2 75%
3 56%
4 42%
5 32%
6 23%
7 18%
8 13%
9 10%

The probability of our reaching the ninth round is only 10%; this means that if we play this game 1000 times, we’ll only get to the ninth round about 100 of those times; this isn’t likely to be a long game. Since we know the expected gain of each round, we expect to make \(0.25\$ * 8 = 2\$\) if we voluntarily stop after the eighth round. So, here’s our strategy: pick the risk you’re willing to take, figure out the expected payoff if you play for that many rounds, play the game until you reach that payoff, and then stop. In our case, if you can stomach a 90% risk of failure, you’re expecting to make 2$, so play the game until you make 2$, and stop.

Our problem is similar to optimal stopping problems. The most common example is probably the secretary problem, which seems hard, but has a deceivingly simple solution. The problem in its pure form reads:

Ask someone to take as many slips of paper as he pleases, and on each slip write a different positive number. The numbers may range from small fractions of 1 to a number the size of a googol (1 followed by a hundred 0s) or even larger. These slips are turned face down and shuffled over the top of a table. One at a time you turn the slips face up. The aim is to stop turning when you come to the number that you guess to be the largest of the series. You cannot go back and pick a previously turned slip. If you turn over all the slips, then of course you must pick the last one turned.


A variant of this game came up in Trial of the Clone, an interactive fiction by Zach Weinersmith, the difference being that the goal was to surpass a certain score, rather than just maximize it. In my case, I had to make 2 points, which I did early on, but kept playing not realizing just how lucky I must have been.