Recursive expected value and the re-roll family

PROB · Chapter 312 min readAsked at Jane Street, Optiver, SIG, IMC

Assumes Conditioning: the tower property.

After this lesson you should be able to

  • Price a game where you may pay to try again, using a threshold strategy.
  • Set up and solve the self-referential equation for a game that can repeat forever.
  • Explain why the optimal threshold equals the value of the game itself.

The single most-asked interview question type: you roll a die, then choose whether to roll again. These are optimal-stopping problems, and every one of them is solved by the same two moves — condition on the first outcome, and recognise that the continuation value is the value of the whole game.

The family of questions

Interviewers escalate through a fixed sequence: one roll, then one optional re-roll, then a re-roll that costs money, then unlimited re-rolls, then the same thing on a d100d100. Each step is a small change to the same equation. Knowing the shape means you are answering the fifth version while other candidates are still deriving the second.

Example 3.34

Stage 1 — one roll

You are paid the face value of a single roll of a fair six-sided die. What is a fair price?

Show the worked solutionHide the worked solution

Worked solution

  1. Formula
    E[X]=∑i=16i⋅Pr⁡(X=i)\mathbb{E}[X] = \sum_{i=1}^{6} i \cdot \Pr(X = i)
  2. Substitute
    =16(1+2+3+4+5+6)= \frac{1}{6}(1 + 2 + 3 + 4 + 5 + 6)
  3. Solve
    =216= \frac{21}{6}
  4. Answer
    E[X]=3.5\mathbb{E}[X] = 3.5

Example 3.35

Stage 2 — one optional free re-roll

You roll once, then choose whether to re-roll. If you re-roll you are paid whatever the second roll shows. What is a fair price?

Show the worked solutionHide the worked solution

Worked solution

  1. Formula
    E=∑i=1616max⁡ ⁣(i, E[re-roll])\mathbb{E} = \sum_{i=1}^{6} \frac{1}{6}\max\!\left(i,\ \mathbb{E}[\text{re-roll}]\right)
  2. Substitute
    E[re-roll]=3.5, so keep i when i>3.5\mathbb{E}[\text{re-roll}] = 3.5, \text{ so keep } i \text{ when } i > 3.5
  3. Solve
    Re-roll on {1,2,3}, keep {4,5,6}\text{Re-roll on } \{1,2,3\}, \text{ keep } \{4,5,6\}
    Keep anything strictly better than what a fresh roll is worth.
  4. E=36(3.5)+16(4+5+6)\mathbb{E} = \frac{3}{6}(3.5) + \frac{1}{6}(4 + 5 + 6)
  5. =1.75+2.5= 1.75 + 2.5
  6. Answer
    E=4.25\mathbb{E} = 4.25

Sanity check. Must exceed 3.53.5: the option to re-roll can be declined, so it cannot be worth less than nothing.

First rollShows 4, 5 or 6 — keep it50%worth 5 on averageShows 1, 2 or 3 — re-roll50%worth 3.5
Figure 3.36 · The free re-roll, in one picture. Keeping beats re-rolling exactly on the faces above 3.53.5, so the split is at the middle. Half the time you hold an average of 55 and half the time you take a fresh roll worth 3.53.5, which is the 4.254.25 above. Every later stage moves only where the split falls.

Example 3.37

Stage 3 — the re-roll costs $1

Same game, but re-rolling costs you $1\$1. What is a fair price now?

Show the worked solutionHide the worked solution

Worked solution

  1. Formula
    E=∑i=1616max⁡ ⁣(i, 3.5−1)\mathbb{E} = \sum_{i=1}^{6} \frac{1}{6}\max\!\left(i,\ 3.5 - 1\right)
  2. Substitute
    Re-roll is worth 2.5, so keep i when i>2.5\text{Re-roll is worth } 2.5, \text{ so keep } i \text{ when } i > 2.5
  3. Solve
    Re-roll on {1,2}, keep {3,4,5,6}\text{Re-roll on } \{1,2\}, \text{ keep } \{3,4,5,6\}
  4. E=26(2.5)+16(3+4+5+6)\mathbb{E} = \frac{2}{6}(2.5) + \frac{1}{6}(3 + 4 + 5 + 6)
  5. =56+186=236= \frac{5}{6} + \frac{18}{6} = \frac{23}{6}
  6. Answer
    E=236≈3.833\mathbb{E} = \frac{23}{6} \approx 3.833

Sanity check. Between 3.53.5 and 4.254.25: the option still has value, but the fee has eaten a third of it. The option is worth nothing only once the fee reaches 2.52.5, at which point the continuation drops to 11 and you would never re-roll anything.

Proposition 3.38

Stage 4 — unlimited re-rolls, each costing 11

Now the continuation is not a single fresh roll but *the same game again*. Let VV be the value of the game. If you re-roll you pay 11 and find yourself facing a game worth VV, so the continuation is worth V−1V - 1. You therefore keep any roll above V−1V - 1, and that threshold is what makes the equation close on itself.

Holds when

  • The game must be genuinely identical after a re-roll — same die, same rules, same remaining rolls.
  • The threshold must be consistent with the VV it produces, which is what solving the equation enforces.

The rest of this lesson is in Premium

You have read the opening. 10 more sections follow, including 4 worked examples and 3 quick checks.

Start the free 7-day trialSign in

Nothing is charged for 7 days, and you can cancel before then. Or read Arithmetic that survives a clock in full, free.