2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ W.r.t. to the last sentence, isn't that because $E=3.5$ when rolling a dice under normal circumstances? $\endgroup$ – Bobson Dugnutt Sep 12 '16 at 20:10
  • $\begingroup$ Thank you very much for the precise formula. Does the formula holds for the square case? $\endgroup$ – richitesenpai Sep 13 '16 at 1:15
0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Hello there. Thanks for your response. I am not understanding the squared case. To be more precise, I am not understanding when you say "you should average the squares of the rolls". Can you please do one case to see how is done. Thanks $\endgroup$ – richitesenpai Sep 13 '16 at 1:13
  • $\begingroup$ Just as above... for each possible set of keepers, find the average of the squares of those rolls. $\{1\}\rightarrow 1$; $\{1,6\}\rightarrow 18.5$; $\{1,5,6\}\rightarrow 20.67$; $\{1,4,5,6\}\rightarrow 19.5$; $\{1,3,4,5,6\}\rightarrow 17.4$, and $\{1,2,3,4,5,6\}\rightarrow 15.17$. $\endgroup$ – mjqxxxx Sep 13 '16 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.