Mistake in question 2

[GillesVandewiele]

There's a mistake in question 2. I think the optimal strategy would be to re-roll if first roll <= 3.

You only calculate probabilities but one should look at the expected value. One should only perform a second roll when its expected value is larger than what we currently have by our first roll.

first roll	Expected value second roll
1	1/8 * (2 + 3 + 4 + 5 + 6 + 7 + 8) = 35/8
2	1/8 * (3 + 4 + 5 + 6 + 7 + 8) = 33/8
3	1/8 * (4 + 5 + 6 + 7 + 8) = 30/8
4	1/8 * (5 + 6 + 7 + 8) = 26/8
5	1/8 * (6 + 7 + 8) = 21/8
6	1/8 * (7 + 8) = 15/8
7	1/8 * (8) = 1
8	0

As soon as the first roll = 4, the expected value that we obtain by making a second roll is lower than the value we already have. As such, optimal strategy is to re-roll when first roll <= 3.

Another extra question that could be asked here is how much you would be willing to bet. For this, we can calculate the expected value of this game. For first roll equal to 1, 2 or 3, we take the expected value of the second roll. For the others, we take the expected value of the first roll.
Giving us: E[X] = 1/8 * (35 / 8 + 33 / 8 + 30 / 8 + 4 + 5 + 6 + 7 + 8) = 5.28125
--> We are willing to bet anything lower than this value.

One could calculate this for an alternative strategy as well. E.g. re-rolling when first roll <= 4 gives us:
E[X] = 1/8 * (35 / 8 + 33 / 8 + 30 / 8 + 26/8 + 5 + 6 + 7 + 8) = 5.1875

Simulation in Python (ugly code!)

>>> import numpy as np
>>> reward_3 = []
>>> reward_4 = []
>>> for _ in range(1_000_000):
...   r1 = np.random.randint(1, 9)
...   if r1 <= 3:
...     strat1 = r1 + np.random.randint(1, 9)
...   else:
...     strat1 = r1
...   if r1 <= 4:
...     strat2 = r1 + np.random.randint(1, 9)
...   else:
...     strat2 = r1
...   if strat1 > 8:
...     strat1 = 0
...   if strat2 > 8:
...     strat2 = 0
...   reward_3.append(strat1)
...   reward_4.append(strat2)
... 
>>> print(np.mean(reward_3))
5.280888
>>> print(np.mean(reward_4))
5.186363

Notice how the average rewards our expected values very well (law of large numbers)

[dastenturlin]

Hey! @GillesVandewiele could you explain this assumption please? Shouldn't we look at the sum of the throws?

One should only perform a second roll when its expected value is larger than what we currently have by our first roll.

[GillesVandewiele]

The question states: You get to roll the die once, see the result, and then may choose to either stop or roll again.

So you roll once and then you decide to roll the second die or not. Rolling a second die has the risk of going bust, so you should only do it if you rolled a low number with your first die (3 in this case).

[matthewdippel]

I think a simple way to do the calculations in this problem is to condition on not going bust with a second roll, and then look at the expected value conditioned on that. This works since in the events where you bust, the expected value of the game is zero, so those events zero out.

E[rerolling at value x] = Pr[don't go bust when rerolling at value x] * (E[old roll + new roll | old roll + new roll <= 8]

When you condition on not going bust, the expected new value is just the average of all sums that wouldn't make you bust. For example, if x=4, you can sum to 5, 6, 7, or 8, which average to 6.5.

= (1 - x/8) * (((x+1) + 8)/2)
= (1 - x/8) * (x/2 + 4.5)

You can substitute a few values of x and find out when the expected value is no longer greater than x, which is probably appropriate given the time constraints. At x=3, you get (5/8)(6) > 3, and at x=4 you get (1/2)(6.5) < 4.

[kstoneriv3]

Can't we roll the dice more than two times? If we can, I guess the dynamic programming approach works. By letting V_k be the expected payoff of the best strategy when the current sum is k, we can have recursive relation

V_k = max{k, sum{V_l / 8: k < l <= 8}}.