| title |
slug |
tags |
date |
Threshold Rule: Rolling a Die |
threshold-rule-rolling-a-die |
zettel |
threshold-rule-rolling-a-die |
threshold-rule |
statistics |
probability |
mathematics |
algorithms-to-live-by |
book |
book/algorithms-to-live-by |
brian-christian |
tom-griffiths |
brian-christian-and-tom-griffiths |
|
2021-12-29T09:16 |
A rudimentary application of the #[[5b12ca91|Threshold Rule]] is when rolling
a die. A general rule of thumb for solving optimal stopping problems is thinking
backwards or using [[95485766|backward induction]].1 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.
