# Best Strategy for a die game

You are allowed to roll a die up to six times. Anytime you stop, you get the dollar amount of the face value of your last roll.

Question: What is the best strategy?

According to my calculation, for the strategy 6,5,5,4,4, the expected value is $142/27\approx 5.26$, which I consider quite high. So this might be the best strategy.

Here, 6,5,5,4,4 means in the first roll you stop only when you get a 6; if you did not get a 6 in the first roll, then in the second roll you stop only when you roll a number 5 or higher (i.e. 5 or 6), etc.

-

Let $X_n$ be your winnings in a game of length $n$ (in your case $n = 6$), if you are playing optimally. Here, "optimally" means that at roll $m$, you will accept if the value is greater than $\mathbb{E} X_{n-m}$, which is your expected winnings if you continued to play with this strategy.

Let $X \sim \mathrm{Unif}(1,2,3,4,5,6)$ (you can also insert any distribution you like here). Then $X_n$ can be defined as $X_1 = X$ and for $n \geq 2$,

$$X_n = \begin{cases} X_{n-1}, \quad \mathrm{if} \quad X < \mathbb{E}X_{n-1} \\ X \quad \mathrm{if} \quad X \geq \mathbb{E}X_{n-1} \end{cases}$$

So your decisions can be determined by computing $\mathbb{E} X_n$ for each $n$ recursively. For the dice case, $\mathbb{E} X_1 = \mathbb{E}X = 7/2$ (meaning on the fifth roll, accept if you get >7/2, or 4,5 or 6), and so,

$$\mathbb{E} X_2 = \mathbb{E} X_1 \mathrm{P}[X = 1,2,3] + \mathbb{E} [X | X \geq 4] \mathrm{P}[X = 4,5,6]$$ $$= (7/2)(3/6) + (4 + 5 + 6)/3 (1/2) = 17/4$$

So on the fourth roll, accept if you get > 17/4, or 5 or 6, and so on (you need to round the answer up at each step, which makes it hard to give a closed form for $\mathbb{E} X_n$ unfortunately).

-

Just work backwards. At each stage, you accept a roll that is >= the expected gain from the later stages:
Expected gain from 6th roll: 7/2
Therefore strategy for 5th roll is: accept if >= 4
Expected gain from 5th roll: (6 + 5 + 4)/6 + (7/2)(3/6) = 17/4
Therefore strategy for 4th roll is: accept if >= 5
Expected gain from 4th roll: (6 + 5)/6 + (17/4)(4/6) = 14/3
Therefore strategy for 3rd roll is: accept if >= 5
Expected gain from 3rd roll: (6 + 5)/6 + (14/3)(4/6) = 89/18
Therefore strategy for 2nd roll is: accept if >= 5
Expected gain from 2nd roll: (6 + 5)/6 + (89/18)(4/6) = 277/54
Therefore strategy for 1st roll is: accept only if 6
Expected gain from 1st roll: 6/6 + (277/54)(5/6) = 1709/324

So your strategy is 6,5,5,5,4 for an expectation of \$5.27469...

-
Just thought I would add that TonyK's answer is an example of dynamic programming: en.wikipedia.org/wiki/Dynamic_programming –  Mike Spivey Dec 14 '10 at 16:35
Is there a proof that this kind of consideration always yields the best strategy? –  TCL Dec 14 '10 at 16:36
@TCL: The proof is right there in my Answer. If that's not a proof for you, I don't know what is. –  TonyK Dec 14 '10 at 16:39
@TCL: TonyK's solution maximizes the expected payoff over all stopping time strategies. You can find more examples and a bit of the theory in Section 3 of my notes at stat.ualberta.ca/~schmu/stat580/2011notes.pdf In particular, I solve a very similar die problem in Example B-5 on page 45. –  Byron Schmuland Dec 14 '10 at 16:44

On the next to last roll, the expectation on the last roll is 3.5, so accepting 4 and rejecting 3 is clearly right. On the third to last roll, you should calculate the expectation if you decline. You have 1/2 chance of rolling 4 or better and accepting it, with an expectation of 5. You have 1/2 chance of rolling 3 or worse and rejecting it, with an expectation of 3.5. So if you decline the third to last, you expect 4.25. So you should reject a 4 and accept a 5. If you keep working backwards like this, you may find you should bump at least one of your 5's to a 6.

-