Suppose there is a game in which you roll a fair, 6-sided die and win dollars equal to the outcome of the roll. How much would you expect to win on average?
Suppose, if you don’t like the outcome of the roll, you can reroll the die once, and win dollars equal to the outcome of the 2nd roll (once you choose to reroll, you can no longer go back to the 1st roll). How much would you expect to win on average?
Suppose, if you don’t like the outcome of the 2nd roll, you can reroll the die once more, and win dollars equal to the outcome of the 3rd roll (once you choose to reroll, you can no longer go back to previous rolls). How much would you expect to win on average?
This was an actual brain teaser question once asked at Jane Street for an interview for an intern role.
Solution
For a single roll, the expected winnings are just the possible outcomes divided by the probabilities: (1 + 2 + 3 + 4 + 5 + 6) / 6 = 3.5
When you are allowed to reroll the die once, you need to think about when you would actually choose to reroll. If you roll a 4, 5, or 6 on the first roll, you would not choose to reroll, because those are higher than what you would expect to win on a single roll (3.5, as we showed above). This means half the time you reroll and expect to get 3.5, and half the time you get the average of 4, 5, and 6, so your expected winnings are: (4 + 5 + 6) / 6 + 3.5 / 2 = 4.25
Finally, if you are allowed to reroll the die up to twice, you use the same logic as above. After your first roll, you know the next two rolls would give you expected winnings of 4.25, as we showed above. So you would reroll if your first roll was lower than 4.25, and you would keep if your first roll was 5 or 6. That means your expected winnings are: (5 + 6) / 6 + 4.25 x 2/3 = 4.66667