Best strategy for a fair die game provided if its shows 1 you stop.

Question

Here is the problem.

You roll a conventional fair die repeatedly. If it shows 1, you must stop, but you may choose to stop at any prior time. Your score is the number shown by the die on the final roll. What stopping strategy yields the greatest expected score? what strategy would you use if your score were the square of the final roll?

I have been trying to solve this problem for a few days and still have no clue on how to solve it. Can someone provide me the technique on how to solve this type of problems.

Answer 1

Note that whether you roll again or not should be entirely based on the previous roll. That's because the eventual result is the same whatever you do.

Now, if you stop after rolling $i$, then you should stop after rolling anything bigger than $i$.

And if you continue when you roll an $i$, you just continue after any roll smaller than $i$.

Then if the last roll is $i$, for $i=2,3,4,5,6$ then:

Stopping after an $i$ result yields $i$.

Continuing after an $i$ result yields $E$.

So let $j$ be the largest roll on which continue

The the expected value $E_j$ is:

$$ \begin{align}E_j&=\frac{1+(j-1)E_j+(j+1)+(j+2)+\cdots + 6}{6}\\ &=\frac{1+(j-1)E_j+j(6-j)+(1+2+\cdot+6-j)}{6}\\ &=\frac{1+(j-1)E_j+j(6-j)+\frac{(6-j)(7-j)}{2}}6\\ &=\frac{1+(j-1)E_j+\frac{(6-j)(7+j)}{2}}6 \end{align}$$

Solve for $E_j$, we get:

$$E_j=\frac{1+\frac{(6-j)(7+j)}2}{7-j}$$

So you want to pick $j$ from $1,2,3,4,5,6$ that maximizes this expression.

So $E_1=\frac{7}{2}, E_2=\frac{19}{5}, E_3=\frac{16}{4}=4, E_4=\frac{12}{3}=4, E_5=\frac{7}{2}, E_6=1$.

Interestingly, this means that two different strategies yield the maximum expected value of $4$.

Answer 2

You're choosing a set of "keepers"... die rolls after which you'll stop rolling... which must include $1$. You want to maximize the average keeper. Clearly if you have $n$ keepers in addition to $1$, they should just be $6,5,\ldots$.

You can find the average explicitly in terms of $n$, but it's easier to just check all the cases: $\{1\}\rightarrow 1; \{1,6\}\rightarrow 3.5; \{1,5,6\}\rightarrow 4; \{1,4,5,6\}\rightarrow 4; \{1,3,4,5,6\}\rightarrow 3.8;$ $\{1,2,3,4,5,6\}\rightarrow 3.5$. So the best you can do is always stop on $5$ and $6$, and on $4$ if you feel like it (it doesn't matter).

In the squared case, the first paragraph stays the same, but when checking the cases you should average the squares of the rolls instead. You'll find that you should again stop on $5$ and $6$; but in this case it hurts to stop on $4$.