You visit a casino, and are offered the chance to play a dice game. The rules are very simple: A single (fair) die is rolled, up-to, six times. At the end of every roll, you are given the chance to “Bank”.
If you bank, you win the dollar amount shown on the dice, and the game stops.
If you elect not to bank, you are committed to roll the die again (you cannot go back). If you do not bank during the first five rolls, then you will automatically bank after the sixth roll and receive whatever it shows.
Question: How much would you pay to play this game?
(Specifically, what is the expected outcome of this game? What is the optimal play strategy?)
How much would you pay to play this game?
Even before delving into some math, it's pretty clear that you'd stop whenever you rolled a six. This is the highest score you could hope to achieve in the game. If you ever roll a six, you would stop immediately.
If you don't roll a six, when there are many rolls to go, you have multiple chances to 'improve' and can hold out in the hope of getting a higher score; the closer you get to the end of the game, the fewer rolls you will have to get a higher number. Intuition tells us that late on in the game you might settle for a score that is 'good enough', but earlier on, with time on your side, you might hold out for the chance of a higher number.
Also, you'd never elect to stop on a one, two or three. Sure, if you got one of these low numbers on the last roll, you have no choice, but if you get a low number earlier on it's clear you should continue rolling (as half the numbers on a die are greater than three).
This highlights the strategy we should employ to solve this puzzle. After each roll we need to decide: Am I better off sticking with what I have, or should I carry on rolling? We can do this by comparing the Expected Values. We know (sum certain), what we can get if we bank now, so what we need to calculate is what the earning potential is if we carry on rolling.
If the earning potential (expected value) is higher than we current have, we carry on rolling.
(Expected value is what would expect to obtain if we were able to run the experiment and infinite number of times, and averaged the results.)
We can solve this puzzle by starting at the end (last roll), and back tracking through each earlier roll.
Let's imagine we're on the last roll. We've been unlucky and now have to accept whatever we get on this last roll as our prize. What is the expected outcome? There are six possible values, each equally likley. The expected outcome is simply calculated by adding them all up, and dividing by six.
The expected outcome is 31/2. If we roll just one die, the expected outcome is 31/2. We have no control on this matter. There is no decission to make.
Now let's consider what we would do if we were on roll #5. If, on roll #5, we currently have a higher expected value than 3.5, we should stop and bank; if we continued on, our expectations go down. If, however, we currently have a lower expected value than 3.5, we should continue to roll #6, as there is a chance to improve.
Values on the die are quantized to integer values; only a roll or 4, 5, or 6 will be higher than 3.5. We can plot all the options in the tree diagram below. Either we roll a 4, 5, 6 (and stop) or we continue on to the next roll. The mathematical way to OR probabilites is to add them. We already know the expected value for roll #6 and, if we stop, we know the score we have. All the data necessary for this calculation is available:
The expected value for roll #5 (two dice in a row) is is 41/4. You can see where this going. Let's look at roll #4 …
If, on roll #4, we currently have a higher expected value than 4.25, we should stop and bank; if we continued on, our expectations would go down. If, however, we currently have a lower expected value than 4.25, we should continue to roll #5, as there is a chance to improve. Below is the tree diagram. This time there are four values for which the expected outcome to come is higher. We only bank if we roll a 5 or 6.
Now we can look at roll #3. Again, only a roll of 5 or 6 is above the expected value of continuing (42/3).
We're getting the hang of this now, onto roll #2:
Finally, we're onto the first roll. From above we can see the expect value on roll #2 is 57/54. This is higher than five. Unless we roll a six on out first roll, it is always in our best interest to carry on. Here's the final tree diagram showing the expected value for the entire game:
And here we have the final answer. The expected value for the game is 589/324 ≈ 5.275
So, if the payout is in dollars, then you should not pay more than $5.28 to play the game!
I don't know about you, but that's a pretty high expected value for the game. If you play optimally, you can score, on average, $5.275 per game. What is the optimal strategy? This is the stop if you you roll 6,5,5,5,4 (or higher) respectively on each of the rolls.Image: rekre89
If you liked this puzzle, you might enjoy reading these other, similar, optimal stopping puzzles.
How to select the best secretary.
Red/Black stopping puzzle (using a deck of cards).
And of course the classic Deal-or-No-Deal.