Double Dice

Solution

Let \[ M=\min(D_1,D_2), \] where \(D_1,D_2\) are independent fair \(20\)-sided dice. The first simple EV fact is \[ \mathbb E[M] = \sum_{k=1}^{20}\Pr(M\ge k) = \sum_{k=1}^{20}\left(\frac{21-k}{20}\right)^2 = \frac{1^2+2^2+\cdots+20^2}{20^2} = \frac{2870}{400} = 7.175. \] So if you had only one future cash-in available after a reroll, a fresh roll is worth \(7.175\) on average. That already gives the right intuition:

- low minimums like \(2,3,4\) are bad, because a reroll is worth more than that,
- high minimums like \(15,16,17\) are amazing, because once you keep them you can collect that amount again and again.

The whole problem is a finite-horizon optimal stopping problem.

Suppose you have already rolled, and the current minimum is \(m\). If there are \(s\) moves left, then you have two real choices:

- keep the current dice forever and cash \(m\) on each of the remaining \(s\) moves, for a total of \( sm, \)
- or throw the current dice away and reroll immediately.

There is never any point in doing something like “cash a few times, then reroll later.” If rerolling is ever worth doing, it is better to do it now. So the decision is always just \[ \text{keep forever} \quad \text{vs} \quad \text{reroll now}. \] That is why the optimal strategy is a threshold strategy. Let \[ R_s \] be the optimal expected profit when you are starting fresh with \(s\) moves left and no current roll saved. Then \[ R_0=0, \] and for \(s\ge 1\), \[ R_s=\mathbb E\!\left[\max\bigl((s-1)M,\;R_{s-1}\bigr)\right]. \] Why? With \(s\) moves left, your first move must be a roll. After that roll, there are \(s-1\) moves left and the observed minimum is \(M\). At that point you either:

- keep it for the remaining \(s-1\) moves, worth \((s-1)M\), or
- abandon it and restart, worth \(R_{s-1}\).

So the Bellman recursion is exactly \[ R_s=\mathbb E\!\left[\max\bigl((s-1)M,\;R_{s-1}\bigr)\right]. \] The distribution of \(M\) is \[ \Pr(M\ge k)=\left(\frac{21-k}{20}\right)^2, \qquad k=1,\dots,20, \] so \[ \Pr(M=m)=\Pr(M\ge m)-\Pr(M\ge m+1)=\frac{41-2m}{400}, \qquad m=1,\dots,20. \] Hence the recursion can be written explicitly as \[ R_s = \sum_{m=1}^{20} \frac{41-2m}{400}\, \max\bigl((s-1)m,\;R_{s-1}\bigr). \] Now for the strategy itself. After a roll, with \(s\) moves remaining, keep the current dice exactly when \[ sm \ge R_s. \] Equivalently, keep whenever \[ m \ge \frac{R_s}{s}. \] So the optimal rule is: \[ \text{with \(s\) moves left, keep iff } m \ge \left\lceil \frac{R_s}{s}\right\rceil. \] That is the dynamic-programming threshold. Running this recursion out to \(100\) moves gives \[ R_{100}\approx 1469.9. \] So the maximum expected total profit is about \[ 1469.9. \] The corresponding optimal thresholds are: \[ \begin{array}{c|c} \text{moves left after you see the roll} & \text{keep if } \min(D_1,D_2)\ge \\ \hline 70\text{ to }99 & 15 \\ 44\text{ to }69 & 14 \\ 29\text{ to }43 & 13 \\ 20\text{ to }28 & 12 \\ 14\text{ to }19 & 11 \\ 10\text{ to }13 & 10 \\ 8\text{ to }9 & 9 \\ 6\text{ to }7 & 8 \\ 4\text{ to }5 & 7 \\ 3 & 6 \\ 2 & 4 \\ 1 & \text{always keep} \end{array} \] So in the actual \(100\)-move game:

- roll first,
- if the minimum is at least \(15\), stop rerolling and just cash that value every remaining move,
- otherwise reroll,
- later, as the number of remaining moves falls, lower your acceptance threshold according to the table.

Intuitively, this makes sense.

Early in the game, one accepted minimum will be collected many times, so you should be picky. A minimum of \(15\) may not sound spectacular on one move, but over a long stretch it is excellent.

Late in the game, there is less time left to exploit a great roll, so you become less selective and are willing to lock in \(14\), then \(13\), then \(12\), and so on.