0
$\begingroup$

I was recently asked this question in an interview. I was able to solve it for two rolls but could not solve it for three or more rolls.

You toss a die and after seeing the outcome, and you are told that you could toss it one more time if you want, with your aim beings to maximize the expected outcome. Under what circumstances would you throw the die a second time? Similarly, what if you are given three trials? If you get 1000 such trials, what would it be?

Just to be clear if you choose to throw the second die then the number on the first die will be discarded and the number on the second die would be taken into account. So when we solve for two die then it comes out that wee should roll the second die only when the number on the first die was 1,2 or 3

$\endgroup$
  • 1
    $\begingroup$ To be clear: if you roll again, you discard the prior rolls, yes? Assuming that, what are your thoughts? Note that your expected outcome on a single toss is $3.5$...when do you think you should roll a second time? (given that you must accept the second toss if you make it). $\endgroup$ – lulu Aug 31 at 17:21
  • 1
    $\begingroup$ @saulspatz Well, you'd roll again because the expected value of the second toss exceeds $3$. Assuming your strategy is "roll again on $3$ or lower, stand on anything greater" then your expected outcome is $6,5,4$ with probability $\frac 16$ each and $3.5$ with probability $\frac 12$, making the expected value $4.25$ in the one time option case. $\endgroup$ – lulu Aug 31 at 17:34
  • 1
    $\begingroup$ @saulspatz continuing: now that we know the expected value of the single option game is $4.25$ we can solve the two option case. That time, of course, we should stand on $5,6$ but roll on $4$ or less, since we expect to do better than $4$ if we move to the single option case. And so on. $\endgroup$ – lulu Aug 31 at 17:37
  • $\begingroup$ Just to be clear if you choose to throw the second die then the number on the first die will be discarded and the number on the second die would be taken into account. So when we solve for two die then it comes out that wee should roll the second die only when the number on the first die was 1,2 or 3 $\endgroup$ – MRIDUL SHARMA Aug 31 at 17:38
  • $\begingroup$ @MRIDULSHARMA Thanks for the clarification. Probably a good idea to edit your post to reflect that, though I think most readers would guess that this was the rule. Do you understand the comments I made to saulspatz? They essentially explain how to solve this problem recursively, on the number of options you have. $\endgroup$ – lulu Aug 31 at 17:42
2
$\begingroup$

For $n≥0$ let $E_n$ be the expected value, under optimum play, of the game given that you have exactly $n$ options.

Clearly $E_0=3.5$ as you are compelled to take whatever you get on the first (and only) roll.

Given that, we can easily compute $E_1$. The optimal strategy is clear...sit on $4,5,6$ and roll again on $1,2,3$. After all, you should only roll again if you expect to do better than what you have. It follows that $$E_1=\frac 16 \times (4+5+6)+\frac 12\times 3.5 =4.25$$

Now, to get $E_2$ we see that strategy must change. This time we'd reject an inital $4$ since we expect to do better than that going forward. Thus $$E_2=\frac 16\times (5+6)+\frac 46\times 4.25 = 4.\overline 6$$

This continues for a bit. Specifically, it continues until we get a value over $5$ at which point our strategy changes. We get that $$E_3=4.9\overline 4=\frac {89}{18}\quad \&\quad E_4=\frac {277}{54}\approx 5.13$$

At this point our strategy changes. If $n≥5$ we must reject an initial $5$, hence for $n≥5$ the recursion becomes $$E_{n+1}=\frac 16\times 6 +\frac 56\times E_n$$

So it is easy to compute $E_n$ for quite large values of $n$. Indeed we can solve that recursion explicitly to get $$E_n=6-\frac {6768}{3125}\times \left(\frac 56\right)^n$$ for $n≥4$.

$\endgroup$

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.