Finite Horizon Stopping

Hard4–5 hrsBackwards InductionDynamic ProgrammingFinite HorizonOptions

Overview

Finite horizon optimal stopping is solved by backwards induction (dynamic programming). You start from the last period (forced stop) and work back, computing the value of having k periods left. The threshold at each period: stop if the current draw exceeds the continuation value. Crucially, earlier periods have LOWER thresholds (be more selective when you have many chances left, more accepting when nearly out of time). This is the fundamental principle behind American option exercise: exercise early only if in-the-money value exceeds holding value.

How to Recognize

→You have EXACTLY N chances to stop
→American option pricing (can exercise at any time up to expiry)
→'You can roll at most N times'
→The horizon matters — unlike infinite horizon, threshold changes each period
→Problem asks for optimal value at each step

Step-by-Step Approach

1.Work BACKWARDS from the last period
2.V_N(x) = terminal payoff (no choice)
3.V_k(x) = max(stop payoff(x), E[V_{k+1}(X')])
4.Threshold at period k: τ_k = smallest x such that payoff(x) ≥ E[V_{k+1}(X')]
5.Thresholds typically INCREASE going backwards (earlier rounds are more lenient)

Key Formulas

V_k(x) = \max\bigl(g(x),\; E[V_{k+1}(X')]\bigr)

— Bellman backwards

\tau_k = \inf\{x : g(x) \ge E[V_{k+1}(X')]\}

V_N = E[X], \; V_{N-1}\text{ stop if }X > V_N,\ldots

(dice/uniform examples)

V_k^{\text{die}} = E[X] + \sum_{j=1}^{k-1} P(X \le V_j)/j \times \text{correction}

Worked Examples

0Quick Example

N=3 dice rolls, keep last. V₃=3.5. V₂: stop if X>3.5 (X≥4). V₂=(1/6)(4+5+6)+(3/6)×3.5=2.5+1.75=4.25. V₁: stop if X>4.25 (X≥5). V₁=(1/6)(5+6)+(4/6)×4.25=1.833+2.833=4.667.

Problem

You roll a fair die repeatedly, up to N times. You must stop at some point and take the value of that roll. What is V_N (optimal expected value with N rolls remaining)?

Solution

V₁ = E[die] = (1+2+3+4+5+6)/6 = 3.5. (One roll left, must take it.)

V₂: Stop now if X > V₁ = 3.5, i.e., X ≥ 4. Otherwise use the 1 remaining roll.

V₂ = P(X≥4)×E[X|X≥4] + P(X<4)×V₁ = (3/6)×5 + (3/6)×3.5 = 2.5+1.75 = 4.25.

V₃: Stop now if X > V₂ = 4.25, i.e., X ≥ 5.

V₃ = P(X≥5)×E[X|X≥5] + P(X<5)×V₂ = (2/6)×5.5 + (4/6)×4.25 = 1.833+2.833 = 4.667.

V₄: Stop if X > V₃ ≈ 4.667, i.e., X = 6.

V₄ = (1/6)×6 + (5/6)×4.667 = 1+3.889 = 4.889.

V₅ = V₆ = ... ≈ 4.889 (diminishing returns; threshold stuck at X=6).

Answer

$V_1=3.5,\; V_2=4.25,\; V_3=4.667,\; V_4\approx4.889,\; V_\infty\approx4.9$ . Thresholds: $\tau_1=1, \tau_2=4, \tau_3=5, \tau_4=6$ . The gain from more rolls rapidly diminishes.

Common Mistakes

!
Working FORWARDS instead of backwards. You MUST start from the terminal condition and work back.
!
Using the INFINITE horizon threshold for a finite horizon problem. With finite N, thresholds change each period.
!
For the dice problem: computing V_k as if you have k-1 remaining rolls AFTER the current one, rather than k rolls total.
!
In option pricing: ignoring the no-early-exercise theorem for American calls on non-dividend stocks (European = American for non-dividend stocks — this is a classic interview pitfall).

Practice Problems

Click "Show Answer" to reveal

You draw from Uniform{1,2,3,4,5} with at most 2 draws (take the last one drawn). What is V₂ (optimal value with 2 draws remaining)?

Hint: V₁ = E[X] = 3. With 2 draws: stop at first draw if X > V₁ = 3, i.e., X ≥ 4.

You have 4 rolls of a die. After each roll you can accept the current value or pay $0.50 to roll again (up to 4 times total, no cost for first roll). What is the expected value of optimal play?

Hint: Incorporate the cost: continuation value at each step = V_{k-1} − $0.50. Stop if current X > V_{k-1} − 0.50.

Back to Study Plan

The Secretary Problem Stopping Problem Variants