Optimal Reroll Strategy for a Die Game

Expectation · Medium · Free problem

You roll a fair $n$-sided die and collect the face value in dollars. At any point before accepting a roll, you may pay $\

$ to reroll. You may reroll as many times as you like. What is your expected earnings under the optimal strategy?

Work through three cases: 1. A 100-sided die (faces

$-
00$) 2. A 1000-sided die (faces
$-
000$) 3. Ten fair 10-sided dice (faces
$-
0$ each), rolled together as a single bundle -- you collect the sum, or pay $\
$ to reroll all ten.

Hints

  1. The optimal strategy is a threshold rule -- find the cutoff above which you stop.
  2. Let $V$ be the value of the game. At the optimal threshold $t^{*}$, you are indifferent between stopping and rerolling: $t^{*} = V - 1$.
  3. Write an equation for $V$ in terms of $t$: the expected payoff given you stop above $t$ plus the expected payoff given you reroll below $t$. Substitute $t = V - 1$ and solve.

Worked Solution

How to Think About It: This is a classic optimal-stopping problem. The optimal policy is a threshold rule: accept the current roll if it is at or above a cutoff, otherwise pay \

and reroll. The cutoff sits where the value of stopping equals the value of continuing. Because a reroll buys a fresh copy of the *same* game (worth $V$) but costs \
, the continuation value is $V-1$, so you accept exactly when the roll is at least $V-1$. The reroll option is most valuable when there is a lot of upside to chase (a wide, heavy-tailed distribution like a 1000-sided die) and least valuable when outcomes are already concentrated near the mean (the sum of ten dice, squeezed together by the CLT).

Quick Estimate: For the 100-sided die the no-reroll mean is $50.5$, but the cheap reroll option clearly adds value, pushing you to accept only high rolls -- somewhere in the high 80s -- so $V \approx 87$. For the 1000-sided die the same logic with far more upside pushes the cutoff into the mid-900s. For ten d10 summed, the distribution clusters tightly around $55$, so the option barely helps and $V$ lands just above the low 60s.

Approach: Set $V = E[\max(X,\,V-1)]$, where $X$ is the roll (or sum). Equivalently, pick the cutoff $t$ = the smallest face with $t \ge V-1$ and solve the self-consistent threshold equation. Solve the fixed point exactly (or by iteration) for each case.

Formal Solution:

For a discrete roll $X$ with reroll cost

$, optimal play accepts when $X \ge V-1$. Writing the cutoff as $t$ (accept $X \ge t$),

$V = \frac{n-t+1}{n}\cdot\frac{t+n}{2} \;+\; \frac{t-1}{n}\,(V-1),$

where the first term is "stop and collect the average of $\{t,\dots,n\}

Loading problems...
quot; and the second is "reroll, paying \
, restarting at $V$." The optimal $t^{*}$ is the smallest face satisfying $t \ge V-1$; equivalently, iterate $V \leftarrow E[\max(X, V-1)]$ to convergence.

Case 1 -- 100-sided die. Solving the fixed point gives the cutoff $t^{*} = 87$ (accept a roll of $87$ or higher) and

$V = \frac{1223}{14} \approx 87.357.$

Case 2 -- 1000-sided die. The wider range means much more upside to chase, so the cutoff climbs to $t^{*} = 956$ and

$V = \frac{8611}{9} \approx 956.778.$

(The key correction over a naive guess: the optimal cutoff is the *smallest* face at least $V-1$, which lands at $956$, giving $V \approx 956.78$ -- not somewhere in the high $960$s.)

Case 3 -- ten 10-sided dice, summed. The sum $X$ ranges

0$-
00$ with mean $55$ and standard deviation $\approx 9.1$. Apply the same fixed point $V = E[\max(X, V-1)]$ over the *sum's* distribution (a clean
0$-fold convolution -- there is no need to enumerate
0^{10}$ outcomes). The optimum is $t^{*} = 63$ (reroll only if the sum is $62$ or below) and

$V \approx 63.736.$

Because the CLT concentrates the sum near $55$, there is little upside to chase, so $V$ only modestly clears the mean -- it does not sit down near $62$ either; the precise fixed point is $\approx 63.74$.

Relative option value. Measuring the option's worth as $V$ minus the no-reroll mean, relative to that mean: the

000$-die gains $\approx +91\%$ (mean $500.5$, $V \approx 956.78$), the
00$-die $\approx +73\%$ (mean $50.5$, $V \approx 87.36$), and the ten-d10 sum only $\approx +16\%$ (mean $55$, $V \approx 63.74$). So the reroll option is worth the most for the
000$-sided die and the least for the ten-dice sum -- exactly because the option pays off through upside spread, which is widest for the
000$-die and nearly absent for the concentrated sum.

Answer: Optimal cutoffs and values are $t^{*}=87,\ V = \tfrac{1223}{14} \approx \$87.36$ (100-sided); $t^{*}=956,\ V = \tfrac{8611}{9} \approx \$956.78$ (1000-sided); and $t^{*}=63,\ V \approx \$63.74$ (ten 10-sided summed). The reroll option is most valuable for the 1000-sided die and least valuable for the ten-dice sum.

Intuition

The indifference condition $t^{*} = V - 1$ is the heart of all optimal stopping problems with a fixed cost: the threshold equals the value of continuing minus the cost. This self-referential equation is what you solve for $V$. It shows up in secretary problems, job search models, and option pricing (where the exercise boundary is where intrinsic value equals continuation value).

The contrast between cases 1 and 3 is important. The 100-sided die has high variance -- lots of spread to exploit -- so the reroll option is very valuable and pushes your expected payoff well above the mean. The ten-dice bundle concentrates outcomes near 55 (CLT at work), so there is little upside to chasing with a reroll. High variance makes optionality valuable. This is exactly why options on volatile assets are worth more, and why volatility is the key input to any option price.

Open the full interactive solver →