Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 4 down vote accepted

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).

share|improve this answer

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.

share|improve this answer

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...

share|improve this answer
1  
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
1  
@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
2  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.