What is wrong with this logic based on a geometric distribution?

Question

Problem #10 from A Collection of Dice Problems by Matthew M. Conroy, is:

Suppose we can roll a $6$-sided die up to $n$ times. At any point we can stop and that roll becomes our score. The goal is to get the highest score possible, on average. How should we decide when to stop?

I approached this by thinking as follows. Suppose I roll a $5$, then the only way I can best that score is by rolling a $6$, which has probability $\frac{1}{6}$. The expected number of rolls to see a 'success' here is $\frac{1}{\frac{1}{6}} = 6$ so I would reroll if I had at least that many rolls left.

This disagrees with the answer given in the site above (see pages 17-18) whose approach was different and whose summary is as follows:

(...) We can summarize the strategy as follows:

• If there are at least 5 rolls left, stick only on 6.
• If there are 4, 3, or 2 rolls left, stick on 5 or 6.
• If there is only 1 roll left, stick on 4, 5 or 6.

I don't get what is wrong with my line of reasoning though.

Answer 1

What's wrong with your approach is that it has almost nothing to do with the game.

If you roll a $5$ and decide to roll again, you cannot go back and claim that $5$ as your score. So the question is not, "Will I roll a six in the remaining rolls?" Rather, the question is, "If I decide to roll again and play the remaining rolls optimally, what is my expected final score?"

The expected final score includes not only the possibility that you might roll a $6$, but also the possibility that you might end up with a score of $1$. Or $2$, or $3$, or $4$, or $5$. We get the expected value by multiplying each score by the probability that you will end up with that score, and add up the resulting numbers to get your expected value.

The expected value is generally considered a good way to take into account the fact that you might lower your score by deciding to roll again, a possibility that (as a comment pointed out) your approach does not account for. In that sense, your approach is unrealistically optimistic about rolling again.

On the other hand, the expected wait until the next $6$ takes into account the possibility that it might take $7$ rolls, or $8$, or $9$ until a six appears, each of those possibilities multiplied by its own probability. But if you only have six rolls left, it doesn't make any difference to you whether it would take $7$, $8$, $9$, or more rolls to get a six, because you cannot make those rolls. In that sense, your approach is unrealistically pessimistic about rolling again.

So not only does your approach not tell us exactly how many rolls must remain to make it worthwhile to re-roll on a $5$, it does not even give us either a lower or upper bound for the number of rolls. The required number of rolls might be more or less than six depending on whether your algorithm's error on the optimistic side outweighed its error on the pessimistic side, or vice versa.

TLDR: The waiting time until the next $6$ doesn't tell us anything about how to play this game.

Answer 2

You're not guaranteed to see a six after 6 rolls - to solve the problem you need to think in terms of expected value.

The answer given in the link works by using a recursion - to do this you start from the simplest case (n=1 roll allowed), and work upwards. If you're only allowed one roll there is no decision to make. If you're allowed two rolls, then the only decision to make is whether to stop after the first roll or not. You would roll again if, on average, you expect the result of the second roll to be better than the first. The expected value of each roll is 3.5 -calculated by [1/6 *(1+2+...+6)]. So you would only use your second roll if E[second roll] > [observed value on first roll]. i.e. if you got three or less on first roll you would roll again. Using this strategy will maximise your average score if only allowed two rolls.

So now we have an average score after two rolls. What about three rolls? This breaks down into two decisions: (i) I have two rolls left should I stop after the first roll? (ii) I have one roll left should I stop after the second roll? Case (ii) above is the same as if n=2 from the start, so the strategy here (and its expected value) is already defined above. Given that we know this strategy and the expected value (4.25), then we should decide to stop if our score after the first roll is already better than the score we expect to get with two further rolls. i.e. if n=3 then stop if we get 5 or 6 on the first roll.

So next to define a recursion for general n:

If f(n) is our expected score after n rolls (using the best possible strategy), then using the above argument you can express f(n) as a recursion using f(n-1):

f(n) = f(n-1) * floor(f(n-1))/6 + 1/6*[floor(f(n-1)+1 ... + 6 ]

The second term above represents the "contribution" from sticking on your current roll, and the first term represents the "contribution" from the remaining rolls

This is the recursion written in the answer, but the author expressed it for a general die with s sides.