A game with an $n$-sided die

diceexpected valuegame theoryoptimizationprobability

Suppose you play a game with a fair $n$ sided die (that, if being rolled yields us a discrete random variable uniformly distributed on $\{k \in \mathbb{N}| k \leq n\}$).

You play the following game:

You start by rolling this die. Every time you roll it you may choose either to quit the game or take a reroll. When you quit the game your score becomes equal to $(N_l – N_r)$, where $N_l$ is the result of your last roll and $N_r$ is the number of rerolls you have taken.

What is the optimal way to play to maximize your expected score?

What thoughts do I have on that matter:

If you have already more than $n – 1$ times, as it would guarantee your score to be non-positive (and thus definitely less than it could have been if you have stopped before)

If $n$ or $n – 1$ is the result of your last roll, then there is no need to reroll, as any score you will be able to get after retooling will definitely not exceed the score, that you will get, if you quit immediately.

However, those two thoughts are clearly not enough to construct the optimal strategy.

Best Answer

Assuming for simplicity you are not allowed to play game infinitely (for example you are forced to quit if you roll $n$), then the game is "either take what you rolled or pay $1$ and play again". Lets say that we get maximum expected score using strategy $f$ "take roll if you rolled at least $k$, otherwise switch to strategy $g$".

$\mathbb E f = \frac{n - k + 1}{n} \cdot \frac{k + n}{2} + \frac{k - 1}{n} \left(\mathbb E g - 1\right)$

So, as $f$ gave as maximum score, we would be at least not worse if we switch back to $f$ instead of $g$. This gives us equation $x = \frac{n - k + 1}{n} \cdot \frac{k + n}{2} + \frac{k - 1}{n}\left(x - 1\right)$, so our score is $\frac{k^2 + k - n^2 - n - 2}{2(k - n - 1)}$. Maximizing it gets $k = n - \sqrt{2n} + 1$ (of course we need to round it up or down depending on $n$).

Related Question