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?
On
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}$.