Threshold Rule: Rolling a Die

A rudimentary application of the #Threshold Rule is when rolling a die. A general rule of thumb for solving optimal stopping problems is thinking backwards or using backward induction.¹ A standard die with a maximum roll of 6 assuming there are equal chances of rolling any face of the die at any given roll, let \(k\) equals to the remaining retry. At zero remaining reroll, we set up the base case which has an average value of a die roll of 3.5 \(((1+2+3+4+5+6)/6)\), an average of all value of the die since any value would be better than nothing since its the last roll.

Using the Threshold Rule, on the second to last roll where \(k = 1\), you should stop at any value greater than 3.5 (roll of 4 or higher). At this point, there is a 50% chance of rolling 1, 2 or 3–values less than the average of 3.5 and be better off chancing the final roll–and a 50% chance of rolling 4, 5, or 6 (averaging 5). Therefore, the average for \(k = 1\) is 4.25 \(((5.0 + 3.5)/2)\) and should only consider another roll at \(k = 2\) when the die rolled higher than the average of 4.5. Following the strategy, let \(\mu(k)\) equals the average value of a roll at a given remaining rolls \(k\),

$$ \begin{aligned} \mu(0) &= \frac{(1+2+3+4+5+6)}{6} = 3.5 \\ \mu(1) &= \frac{\mu(0)+\frac{(4+5+6)}{3}}{2} = 4.25 \\ \mu(2) &= \frac{\mu(0)+\mu(1)+\frac{5+6}{2}}{3} = 4.42 \\ \mu(3) &= \frac{\mu(0)+\mu(1)+\mu(2)+\frac{5+6}{2}}{4} = 4.42 \\ \mu(4) &= \frac{\mu(0)+\mu(1)+\mu(2)+\mu(3)+\frac{5+6}{2}}{5} = 4.42 \\ \mu(5) &= \frac{\mu(0)+\mu(1)+\mu(2)+\mu(3)+\mu(4)+\frac{5+6}{2}}{6} = 4.42 \\ \end{aligned} \\ \cdots $$

The algorithm seems to converge to \(p = 4.42\) as \(k\) approaches \(\infty\) as early as \(k = 2\). Therefore, with the algorithm and the Threshold Rule, keep chancing for a roll of 5 or 6 until there are 2 remaining rolls left, then settle for anything greater than 3.5 at \(k = 1\). However, of course, at \(0\) remaining roll, the optimal stopping strategy fail to stop at anything at all which is an obvious flaw of the Threshold Rule.