One Reroll Allowed

Question

Roll a fair die. You may either keep the result or reroll once and keep the second roll. Playing optimally, what is the fair value of this game?

Accepted Answer

Work backwards. A reroll is a plain die roll worth 3.5. So the optimal rule on the first roll: keep 4, 5, 6 (each beats 3.5), reroll 1, 2, 3. mathbbE = underbracefrac36_textkeep cdot frac4+5+63 + underbracefrac36_textreroll cdot 3.5 = frac12 cdot 5 + frac12 cdot 3.5 = 4.25. The option to reroll is worth 4.25 - 3.50 = 0.75. This is option pricing in miniature: the right (not obligation) to retry adds value, the optimal exercise rule is a threshold ("keep iff above continuation value"), and the value of the game is the expectation under that rule. Every dynamic-programming game in these interviews has this shape: compute continuation value, compare, fold backwards.

One Reroll Allowed

Problem

Your answer

Hints

More Expected Value to train on