probability - Expected outcome for repeated dice rolls with dice fixing

Here is another dice roll question.

The rules

• You start with n dice, and roll all of them.


• You select one or more dice and fix them, i.e. their value will not change any more.


• You re-roll the other dice.



• Repeat that until all dice are fixed (after at most n rounds).

The final score is the sum of the values of all n dice. Assume you want to maximize the expected score.

The questions

• What is the expected score?


• Can the re-rolling strategy be easily phrased?



• Are there situations (possibly for slightly larger n) where you would re-roll a 6?

Thoughts

It seems to be counter-intuitive to re-roll a 6, but it would give you one extra roll for all other dice, so maybe it is worth it? Or is there an argument disproving this hypothesis, even without answering the first two questions?

Further reading

I wrote a narrative about this question and the answers on my blog post.

Answer

For standard six-sided dice, $v_{199}-v_{198}\approx6+9\cdot10^{-21}$. Here's the code I used to compute this value. The numbers are represented exactly as rationals, so rounding errors are excluded.

The basic idea is to keep track of two values for each $n$: the value $v_n$ of the game with $n$ dice and the value $w_n$ of the game when preceded by a free roll without $6$s and without the requirement to fix at least one die. For $n\ge6$, we have $v_n\gt5n$, so the free roll becomes worthless and $w_n=v_n$. Thus we only have to calculate $w_n$ and $v_n$ separately up to $n=5$, and as long as the optimal strategy fixes all $6$s, for $n\gt6$ we can calculate $w_n=v_n$ as

\begin{align}
w_n
&=6^{-n}\left(5^n(w_{n-1}+5)-\sum_{d=1}^4d^n+\sum_{k=0}^{n-1}\binom nk5^k\left(w_k+6(n-k)\right)\right)\\
&=C_n+6^{-n}\left(\sum_{k=0}^n\binom nk5^kw_k-5^n(w_n-w_{n-1})\right)\;,
\end{align}

where in the first equation the first term corresponds to the case without $6$s, the second term corrects for the fact that the highest die in that case need not be a $5$, and the sum in the third term is over the number $k$ of non-$6$s; and where

$$C_n=n+6^{-n}\left(5\cdot5^n-\sum_{d=1}^4d^n\right)\;,$$

as defined in Milo Brandt's answer, is the expected value of the dice to be fixed either as $6$s or as the highest die. (This is essentially the modification of Milo's approach to account for the exceptions at small $n$, as suggested in his answer.)

Since the calculation yields $v_{199}-v_{198}\gt6$, the optimal strategy for $200$ dice does not fix the second of exactly two $6$s. Beyond that, the calculation is no longer valid, since it assumes that $6$s are always fixed.

I added this question here as an answer to Examples of apparent patterns that eventually fail.

I'm leaving the original answer up in case the process that led to the solution is of any interest.

---

---

Here are some results vor $v_n-v_{n-1}$ for other dice. They don't settle the concrete question for standard six-sided dice, but they indicate why it's so difficult to settle, and they disprove the intuition discussed in the question that the highest number should never be re-rolled.

For three-sided dice with numbers $0,1,1$:

1 : 0.666666666666666
2 : 1.037037037037037
3 : 1.050754458161865
4 : 1.036156412470998
5 : 1.023458163050328
6 : 1.01495109027056
7 : 1.00954958850473
8 : 1.0061461980586
9 : 1.003988393919573

and so on, approaching $1$ from above until at least $n=50$. So in this case $1$s should always be rerolled, except if all dice are $1$s. But yet more interesting, for three-sided dice with numbers $1,2,3$:

 1 : 2.0
 2 : 2.555555555555555
 3 : 2.818930041152263
 4 : 2.925621094345374
 5 : 2.966531248686746
 6 : 2.983754306121206

 7 : 2.991943835462998
 8 : 2.996014709747178
 9 : 2.998033031889117
10 : 2.999026265538337
11 : 2.999514808948095
12 : 2.999756553231309
13 : 2.999877305913408
14 : 2.999938178399316
15 : 2.999969029284208
16 : 2.99998464607431

17 : 2.999992480293932
18 : 2.999996346687621
19 : 2.999998215606247
20 : 2.999999102436438
21 : 2.999999522113371
22 : 2.999999727722627
23 : 2.999999837836287
24 : 2.999999904492389
25 : 2.999999948801448
26 : 2.999999978835654

27 : 2.999999997994604
28 : 3.000000008463403
29 : 3.000000012352717
30 : 3.000000011876478
31 : 3.000000009460664
32 : 3.000000006368981
33 : 3.000000003409548
34 : 3.000000000987628
35 : 2.999999999170625
36 : 2.999999998255086

37 : 2.999999998245222
38 : 2.999999998631135
39 : 2.999999999186528
40 : 2.999999999746
41 : 3.000000000210072
42 : 3.000000000535028
43 : 3.000000000716657
44 : 3.000000000774869
45 : 3.000000000741289
46 : 3.000000000657582

47 : 3.000000000549125
48 : 3.000000000434833
49 : 3.00000000036221
50 : 3.000000000285031

(Scroll down to see the results up to $n=50$.) The values are below $3$ for $1\le n\le27$, then above $3$ for $28\le n\le34$, then below $3$ for $35\le n\le40$ and then above $3$ until at least $n=72$, approaching it from above after a local maximum at $n=44$.

These results were obtained with the same code that reproduces Joachim's and Byron's results for standard dice up to $n=7$, so a bug is unlikely.

The results show that general strategy stealing arguments (as suggested by mercio in a comment; I'd also tried to find one) will not work and any proof will have to be based on the specific numbers on the six-sided dice. (A six-sided die with one low and five high numbers behaves much like the three-sided die with one low and two high numbers.)

P.S.: Here are the results for two-sided dice (a.k.a. coins) with numbers $0,1$:

1 : 0.5
2 : 0.875
3 : 1.0
4 : 1.0078125
5 : 1.00634765625
6 : 1.0043106079101562

7 : 1.0027518272399902
8 : 1.0016952995210886
9 : 1.0010172286929446

and so on, approaching $1$ from above roughly exponentially until at least $n=60$.

I'm now running a longer calculation with standard four-sided dice to see whether they eventually follow the pattern of the three-sided dice. So far, up to $n=50$, the differences seem to be approaching $4$ from below roughly exponentially. But note that for the three-sided dice with numbers $1,2,3$, the differences appear to approach $3$ from below roughly exponentially all the way right up to $n=27$, where the difference from $3$ is only $2\cdot10^{-9}$, and then they decide to exceed $3$ after all; so all bets are off.

$Update$: For standard four-sided dice, $v_{70}-v_{69}\approx4-1.5\cdot10^{-13}$ and $v_{71}-v_{70}\approx4+1.7\cdot10^{-13}$. This suggests that we may eventually have $v_n-v_{n-1}\gt6$ for standard six-sided dice after all; and since the switch occurs at $n=28$ for three-sided dice and at $n=70$ for four-sided dice, it may occur at quite high $n$ well over $100$ for six-sided dice. Perhaps the effort we've been putting into proving $v_n-v_{n-1}\lt6$ should better be directed at making larger values of $n$ numerically accessible.