Maximize product of die

Question

Suppose you have two fair 6-sided dice. Your goal is to maximize the product and you are allowed to replace one of the two die with a reroll if you'd like. What is the expected value of the product of these values assuming optimal play?

This is my work however, my python script is getting $\simeq 17.14$. Is my work wrong?

Answer 1

Your work is wrong ($D1$ and $D2$ are not independent) and your script is probably correct. The actual value is $\frac{617}{36} \approx 17.13889$.

To calculate this, consider the expected product for each of the $36$ equally likely pairs of initial rolls if you reroll when the lower initial value is $3$ or less, so $D_1 \times \max(D_2, 3.5)$:

Rolls   1       2       3       4       5       6
                            
1       3.5     7       10.5    14      17.5    21
2       7       7       10.5    14      17.5    21
3       10.5    10.5    10.5    14      17.5    21
4       14      14      14      16      20      24
5       17.5    17.5    17.5    20      25      30
6       21      21      21      24      30      36 

and take the average of the values in the $6\times 6$ array.

This is easy to encode. To find the equivalent with $20$-sided dice in R:

n <- 20 
productwithreroll <- function(x,y){
    ifelse(x > n/2, ifelse(y > n/2, x*y, x*(n+1)/2),
                    ifelse(y > x, y*(n+1)/2, x*(n+1)/2))
    }
mean(outer(1:n, 1:n, productwithreroll))

and this gives $160.20625$, which is $\frac{25633}{160}$.

If you take the slower route and battle through the sums of squares and products etc., you get

for $n$ odd $\dfrac{71{{n}^{4}}+116 {{n}^{3}}+22 {{n}^{2}}-20 n+3}{192n^2}$,

and for $n$ even $\dfrac{71{{n}^{4}}+116 {{n}^{3}}+40 {{n}^{2}}-8 n}{192n^2}$,

both of which are $O(n^2)$, as you might intuitively guess.