Krdytkyu

I was at an interview workshop today and was posed this question:

I keep rolling a die, and my score is the sum of all my rolls. However, if I roll a value I had rolled before, I lose all. What is the optimal strategy?

My attempt is as follows. Suppose I roll $x_1$ on the first turn. On my next turn, my expected gain is

$$frac{21-x_1}{6} - frac{x_1}{6},$$

because I have a $1/6$ chance of rerolling and losing $x_1$, and the remainder of rolls sum up to $21-x_1$, each with probability $1/6$.

Now, suppose my second roll is $x_2$. On the third turn, my expected gain would be

$$frac{21-x_1-x_2}{6}-frac{x_1+x_2}{3}$$

for similar reasons, this time that there is a $2/6=1/3$ instead of $1/6$ chance.

My question is therefore this – given that my analysis was correct (which I am not sure about), how does this translate to a strategy? It is clear that I should roll a second time for any $x_1$, but what does this imply about future rolls? Given that $x_1+x_2=7$ results in an expected gain of exactly zero, should this call for an additional roll if I have hit a sum of $7$? Thanks!

Your analysis only takes into account the possible increase in your score that you get from one more throw (call this the 'immediate increase') rather than from potentially multiple more throws (the 'long-term' increase). As such, your analysis could give the wrong advice and tell you to stop if the expected immediate increase would be less than the expected loss of losing everything, even though your expected long-term increase could actually outweigh that loss.

So, instead of considering what you should do after rolling $1$ die, and then $2$, etc., it is better to first find the point where there is no long-term increase anymore, and then work your way back.

Fortunately, this end point is easy to establish, in that you should never go beyond three rolls: even if you only scored the mimimum sum so far, which would be $1+2+3=6$, you have a probability of $frac{1}{2}$ of losing everything, and so to beat that, you'd need at least two more throws without losing everything, which has a chance of far less than $frac{1}{2}$

Ok, but should you ever go beyond two rolls? Given that we now have established that you should never go beyond three rolls, any increase at this point will only be from any immediate increase.

As such, your formula for having rolled two dice actually turns out to be correct: if after two rolls you have a score of $x$, then the expected gain is
$frac{2}{3}cdotfrac{21-x}{4} - frac{1}{3}cdot
x$, which has a breaking point exactly at $x=7$ ... and what that means is that if after two rolls you have a score below $7$ you should roll again, if the score is above $7$, you should stop, and if your score is exactly $7$, it doesn't matter what you do.

Finally, then, we can move to the situation where you have rolled just $1$ die. Now, here there is actually some potential long-term gain to be had from rolling again, which your formula does not take into account, but since the expected immediate gain already outweighs the expected loss for all possible scores, I agree with you that you should indeed always roll again.