Expected value of a die when decision to role again depends on previous outcome

Question

(Introduction to Probability, Blitzstein and Nwang)

A fair die is rolled some number of times. You can choose whether to stop after 1, 2, or 3 rolls, and your decision can be based on the values that have appeared so far. You receive the value shown on the last roll of the die, in dollars. What is your optimal strategy (to maximize your expected winnings)? Find the expected winnings for this strategy.

My solution:

My strategy would be to role again if the value is less or equal than $3$, because the expected value of the next die is $3.5$.

Let $X_i:=$ value of the $i^{th}$ role of the die, and $C_i:=X_i \leq3$. Then $P(C_i) = P(C_i^c) = \frac{1}{2}$ for $i=1,2$. Let $Y$ be the value of the final roll of the die.

\begin{align} E(Y) &= \frac{1}{4} \left( E(Y|C_1,C_2) + E(Y|C_1,C_2^c) + E(Y|C_1^c,C_2) + E(Y|C_1^c,C_2^c) \right) \\ E(Y) &= \frac{1}{4} ( 2 +5 + 5 +5) = \frac{17}{4} \end{align}

I would then think that in general for $n$ rolls of the die,

$$ E(Y) = \frac{1}{2^{n-1}}(2+5\cdot2^{n-1}), $$

which goes to $5$ for large $n$.

Is this correct? Maybe somebody has a nicer approach to the problem.

EDIT

Based on the answers, I try to come up with an recursive solution

$$w_{j+1}=\sum_{k=4}^6 I_{(E(x)_j, 6]}(k)$$ $$ E(X)_{j+1}^* = \frac{1}{w_{j+1}} \sum_{k=4}^6 k \cdot I_{(E(x)_j, 6]}(k)$$ $$E(X)_{j+1} = \frac{w_{j+1}}{6} E(X)_{j+1}^* + \frac{6-w_{j+1}}{6} E(X)_{j}$$

Answer 1

Scenario $1$: You are allowed one die roll. Your expected value is $3.5$. Let us summarize this by saying $E_1=3.5$.

Scenario $2$: You are allowed up to two die rolls. If your first roll is $3$ or less, you should reroll, since the expectation of your next roll is greater than $3$. If your first roll is $4$ or greater, you should take that value, since if you roll again, your expected value is less than what you have. So in this scenario, half the time you are taking $4, 5, 6$ (equally likely); and half the time you are taking $1, 2, 3, 4, 5, 6$ (equally likely). Thus your expected value here is $E_2=\frac{1}{2}5+\frac{1}{2}3.5=4.25$

Scenario $3$: You are allowed up to three die rolls. If your first roll is greater than $4.25$ (the expected value if you pass on your first roll and go into scenario $2$), you should keep your first roll. Otherwise you should go on and roll again. $E_3=\frac13 5.5+\frac23 4.25=\frac{14}{3}$

Regarding long term behavior, I would think you should be able to approach an expected value of $6$, as the number of allowed die rolls increases.

Answer 2

We can continue with paw88789's solution for arbitrary numbers of rolls. To make the phrasing easier, I'll talk about the $n$th-to-last roll - what really matters here is how many rolls remain, not how many rolls you've already done. We accept the $n$th-to-last roll if it's greater than $E_{n-1}$.

As paw established:

• you have to accept the last roll, and $E_1 = 7/2 = 3.5$.
• you should accept the second-to-last roll if it's at least 4, and $E_2 = 17/4 = 4.25$.
• you should accept the third-to-last roll if it's at least 5, and $E_3 = 14/3 = 4.66\ldots$.

We can continue with this scheme:

• accept the fourth-to-last roll if it's at least 5. Then $E_4 = (1/3) (11/2) + (2/3) (14/3) = 89/18 = 4.94 \ldots$.
• accept the fifth-to-last roll if it's at least 5. Then $E_5 = (1/3) (11/2) + (2/3) (89/18) = 277/54 = 5.12 \ldots$. Now at this point, we accept the $k$th-to-last roll for $k \ge 6$ if, and only if, it's equal to 6. (It's almost surely a coincidence that this works out to be 6.) We get $E_k = (1/6) (6) + (5/6) E_{k-1}$, and it's not hard to expand this to get

$$ E_k = 6 - (47/54) \times (5/6)^{k-5} $$

for $k \ge 5$. This approaches 6, of course, as $k \to \infty$. The basic strategy for a very large number of die rolls (and this should hold up even with a different number of sides) is to hold out for the largest possible value for a long time, and only start accepting lower values in the last few rolls.