(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}$$
Best Answer
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.