expected value of a game with a n sided die

Suppose we have a n-sided die. When we roll it, we can be paid the outcome or we can choose to re-roll by paying $1/n$. What is the best strategy and what is the expected value of this game?

As an approximation, I thought that to get the maximum value $n$ we need to roll $n$ times. So the best strategy is to roll until we get the maximum value $n$ and the expected value should be $n-1$. Is it right as an approximation? How can we calculate the exact best strategy and the exact expected value?

• @ArthurSkirvin Ahh, but you're already paying for 2 rolls, so you're actually at $3 - \frac{2}{6}$, so expectation says roll again (for a d6, that is). – Zimul8r May 21 '14 at 21:48
• @Zimul8r You're right of course, my mistake. Not sure how I came up with that. I was trying to dispute a now deleted comment that suggested the optimal strategy to be to play until you got 4 or more and I got bungled up somehow. Thanks for the correction. – Arthur Skirvin May 21 '14 at 22:23

I believe that your strategy of waiting until you roll the maximum value is optimal.

Let's say that you've rolled a value of $k_i$ on roll $i$ for a total score of $k_i-\frac{i-1}n$. If you can beat your roll of $k_i$ within $n-1$ rolls you'll end up beating your score as well. To demonstrate that let's take the worst-case scenario and say it takes you $n-1$ more rolls to beat $k_i$ and that you only beat it by one so that $k_{i+n-1}=k_i+1$. Your score would then be

$$k_{i+n-1}-\frac{i+n-2}n=k_i+1-\frac{i+n-2}n=k_i+\frac{2-i}n\gt k_i-\frac{i-1}n.$$

So then if the probability of beating your roll of $k_i$ within $n-1$ more rolls (thus beating your score) is greater than 0.5 you should go for it. The probability of doing better than $k_i$ on your next roll is $1-\frac{k_i}n$, so the probability of first doing better than $k_i$ on your $m$th subsequent roll is geometrically distributed:

$$p_M(m)=\left(\frac{k_i}n\right)^{m-1}\left(1-\frac{k_i}n\right)$$

Which means that the probability of doing better than $k_i$ within $n-1$ more rolls is $$\sum_{j=1}^{n-1}p_M(j)=\left(1-\frac{k_i}n\right)\left(\left(\frac{k_i}n\right)^{0}+\left(\frac{k_i}n\right)^{1}+...+\left(\frac{k_i}n\right)^{n-2}\right)=1-\left(\frac{k_i}n\right)^{n-1}$$ So even if $k_i=n-1$ we have that the probability of improving your score within $n-1$ more rolls is $$1-\left(\frac{n-1}n\right)^{n-1}$$

Which increases as $n$ increases. If $n=2$ this would be $0.5$, so for any $n \gt 2$ the probability of improving your score within $n-1$ more rolls even if you've rolled an $n-1$ is greater than 0.5, so you should do it. Thus if you haven't rolled an $n$ it's always best to keep going until you have.

Since the expected number of rolls to get $n$ is $n$, the expected score under this strategy is $n-\frac{n-1}n$ .

Note: Turns out this is not optimal. My strategy depends on looking at the probability of beating your current score with the next roll. In his answer, @ArthurSkirvin looks at the probability of beating it on any subsequent roll. As I should have expected, taking the longer view provides a better strategy.

(I'm assuming an even number of die sides, so there's an $\frac{n}{2}$ side that's the highest side less than the die's $\frac{n+1}{2}$ average.)

Proof: If you rolled $\ \frac{n}{2}$ or less on your $i+1^{st}$ roll and stopped, you have at most $\ \frac{n}{2}-\frac{i}{n}$, whereas the expected value of a reroll (minus the total cost) is $\ \frac{n}{2}+\frac{1}{2}-\frac{i+1}{n}$, which gives you an expected gain of $\frac{1}{2}-\frac{1}{n}$, which is $>0$ for anything bigger than a 2-sided die, so you should re-roll. (But amend the strategy if you're flipping coins.)

If you rolled $\ \frac{n}{2}+1$ or higher on your $i+1^{st}$ roll, you have at least $\ \frac{n}{2}+1-\frac{i}{n}$, whereas the expected value of a reroll (minus the total cost) is still $\ \frac{n}{2}+\frac{1}{2}-\frac{i+1}{n}$, which gives you an expected loss of $\frac{1}{2}+\frac{1}{n}$, which is $>0$, so you should stop.

To compute the expected value of the strategy, $\frac{1}{2}$ the time you roll higher than average on the first roll and stop. Given that you rolled on the upper half of the die, you'll average $\ \frac{3n+2}{4}$. The other half you re-roll.

Half of those times, (now $\frac{1}{4}$ of the total probability), you roll higher than average and stop, this time winning $\ \frac{3n+2}{4}-\frac{1}{n}$ to pay for the re-roll.

The next, you're at $\frac{1}{8}$ of the total probability, and you stop with $\ \frac{3n+2}{4}-\frac{2}{n}$, or re-roll, and so on.

So the expected outcome looks like

$\sum_{i=0}^{\infty} (\frac{3n+2}{4}- \frac{i}{n})(\frac{1}{2})^{i+1}$

For a 6-sided die, that's $4\frac{5}{6}$.

• The expected value of the strategy in the original question (playing until you roll the maximum) seems to have an expected value greater than $4\frac56$ for a d6. Perhaps I'm missing something again, though. Could you explain? – Arthur Skirvin May 21 '14 at 23:01
• Nope, looks like you nailed it. My strategy depends on looking at the probability of beating your current score with the next roll. Yours looks at the probability of beating it on any subsequent roll. As I should have expected, taking the longer view provides a better strategy. – Zimul8r May 22 '14 at 13:00