Data Science Interview Prep: Q64
From Three Rolls to Infinity: Generalizing the Optimal Dice Strategy. (Category: Probability)
Kindly read the ‘How Much Would You Pay to Play This Two-Roll Dice Game?’ newsletter before reading the current newsletter.
Link: How Much Would You Pay to Play This Two-Roll Dice Game?
In the last newsletter, we explored the optimal stopping strategy for a dice game with two rolls. In this edition, we’ll examine the strategy for three rolls and then generalize it to N rolls.
Imagine you’re playing a game where you roll a fair six-sided die up to N times. After each roll (except the last), you can choose to either keep the number rolled or roll again. Your final payout is the number showing on the die when you stop. How much should you be willing to pay to play this game? Specifically, how does this expected payout change when you have exactly three rolls versus a general case of N rolls?
Solution:
(a). Optimal Stopping Strategy for a dice game with three rolls.
1. Understand the expected value of a single roll.
The average value when rolling a fair six-sided die = (1 + 2 + 3 + 4 + 5 + 6)/ 6 = 3.5.
2. Determine the optimal choice after the second roll.
If your second roll is 1, 2, or 3, the value is less than 3.5, so you should roll a third and final time to try for a better outcome.
If your second roll is 4, 5, or 6, it’s better to keep that roll because it is greater than the average expected value of re-rolling (3.5).
The expected value after the second roll, playing optimally, is:
EV2 = 1/6 × (3.5 + 3.5 + 3.5 + 4 + 5 + 6) = 25.5/6 = $4.25.
3. Determine the optimal choice after the first roll.
If your first roll is 1, 2, 3, or 4, the value is less than 4.25 (the expected value from the second roll), so you should roll again.
If your first roll is 5 or 6, it’s better to keep the roll because it is greater than 4.25.
4. Calculate the Overall Expected Value.
Scenario 1: Rolling 1, 2, 3, or 4 on the first roll.
Probability of rolling 1, 2, 3 or 4 on the first roll is 4/6 = 2/3 ≈ 0.667. If this happens, you roll again, and the expected value is 4.25.
Weighted contribution for this scenario = 0.667 × 4.25 = $2.833.
Scenario 2: Rolling 5 or 6 on the first roll.
Probability of rolling 5, or 6 on the first roll is 2/6 = 0.333. If this happens, you keep the roll. The average of 5 and 6 = (5 + 6)/2 =5.5.
Weighted contribution for this scenario = 0.333 × 5.5 = $1.8332.
Combining both scenarios.
The expected payoff of the overall game = $2.833 + $1.8332 = $ 4.6662 ≈ $4.67.
Therefore, $4.67 is the maximum amount you should be willing to pay to play the game.
(b). Generalization: Expected Value for N Rolls.
1. Define EVn as the expected value when you have n rolls remaining.
When you have only 1 roll left, EV1 = $3.5.
For N > 1, you roll once and see x. You can either:
Keep x, or
Roll again, with expected value EVN-1.
So for each x, your payoff = max(x, EVN-1).
2. Calculate weighted contributions and overall expected value.
Each die face x has probability 1/6. So:
This means the weighted contribution for each possible roll x is:
Weighted contribution for x = 1/6 × max(x, EVN-1).
The total expected value EVN is the sum of all these weighted contributions over all possible die faces x = 1 to x = 6.
3. Summary.
To compute the expected value when playing optimally with N rolls, we use a backward induction strategy:
Start by calculating the expected value with just 1 roll: EV1 = 3.5 (the average of a fair six-sided die).
Then, recursively compute EV2 , EV3 ,….,EVN using the formula:
At each stage n, after rolling a value x, compare it to EVN-1 (the expected value if you chose to roll again with n−1 rolls left).
You keep x if x ≥ EVN-1 , otherwise roll again.
The final expected value EVN represents the average payout you can expect from the game with N rolls, assuming you follow the optimal stopping strategy at every step —and therefore, it is the maximum amount you should be willing to pay to play the game.
We hope you found the article both enlightening and valuable! For more insightful content delivered straight to your inbox, simply enter your email address below and hit the subscribe button. Stay tuned for future updates!
Reference:
Dice Game Optimal Stopping Strategy: https://math.stackexchange.com/questions/1472308/optimal-stopping-with-dice-rolls