Questions: Optimal Stopping Theory

Question 1

In the discrete-time optimal stopping problem with finite horizon N, the value function V_n(x) = sup_{τ≥n} E[g(X_τ) | X_n = x] satisfies the backward recursion:

• A. V_n(x) = E[g(X_{n+1}) | X_n = x] for all n
• B. V_n(x) = max{g(x), E[V_{n+1}(X_{n+1}) | X_n = x]} — stop now or continue, whichever is better
• C. V_n(x) = g(x) + E[V_{n+1}(X_{n+1}) | X_n = x] — accumulate the payoff
• D. V_n(x) = min{g(x), E[V_{n+1}(X_{n+1}) | X_n = x]} — minimize expected loss

Answer: (B)

At each time n, you face a choice: stop now (receive g(x)) or continue (receive the expected value of optimal future decisions, E[V_{n+1}(X_{n+1})]). You choose whichever is larger. This dynamic programming recursion, working backward from V_N(x) = g(x), defines the value function at every time and state. The optimal stopping region is {x : V_n(x) = g(x)} — the set of states where stopping is immediately optimal. The continuation region is {x : V_n(x) > g(x)} — where waiting has positive value.

Question 2

The Snell envelope of a payoff process g(X_n) is the smallest supermartingale that dominates g(X_n) for all n. This concept connects optimal stopping to:

• A. Doob's martingale convergence theorem
• B. The Doob-Meyer decomposition — the value process decomposes into a martingale minus an increasing process that captures the 'cost of waiting'
• C. The optional stopping theorem applied in reverse
• D. The law of large numbers for martingales

Answer: (B)

The Snell envelope V_n is a supermartingale (since V_n ≥ E[V_{n+1} | ℱ_n] and V_n ≥ g(X_n)). The Doob-Meyer decomposition writes V_n = M_n - A_n where M is a martingale and A is a predictable non-decreasing process with A_0 = 0. The increasing process A represents the cumulative 'penalty for not stopping' — it increases precisely at times when continuation is strictly suboptimal but the optimal policy would not yet stop. At the optimal stopping time τ*, V_{τ*} = g(X_{τ*}) and A has not yet increased, so the martingale M captures the full value.

Question 3

An American put option on a stock following GBM gives the holder the right to sell at strike K at any time before maturity T. Why can't the American put be priced by the Black-Scholes formula for European options?

Model answer: The European put price assumes exercise only at maturity T. The American put allows early exercise, and this option to stop early has positive value — it is optimal to exercise when the stock falls far enough below K, because the time value of waiting cannot compensate for the immediate payoff K - S. The American put price is the solution to an optimal stopping problem: V(S,t) = sup_τ E_Q[e^{-r(τ-t)}(K-S_τ)⁺ | S_t = S], which leads to a free-boundary problem. The exercise boundary S*(t) — the stock price below which immediate exercise is optimal — must be found as part of the solution. No closed-form formula exists; the price is computed numerically (binomial trees, finite differences, or Monte Carlo with regression).

The free boundary S*(t) divides the (S,t) plane into a continuation region (hold the option) and a stopping region (exercise). In the continuation region, V satisfies the Black-Scholes PDE; in the stopping region, V = K - S. The boundary S*(t) is determined by smooth-pasting conditions: V and ∂V/∂S are continuous across the boundary. This is fundamentally harder than the European case because the domain of the PDE is itself unknown.

Question 4

In the secretary problem (observe candidates sequentially, must hire immediately or lose them), the optimal strategy is to observe the first n/e candidates (approximately 37%) and then hire the next candidate who is better than all previously seen.

• T. True
• F. False

Answer: True

The secretary problem is the most famous discrete optimal stopping problem. With n candidates, the optimal strategy is to reject the first k* ≈ n/e candidates (using them as a 'learning sample'), then accept the first subsequent candidate who is the best so far. This strategy selects the overall best candidate with probability approximately 1/e ≈ 36.8%. The threshold n/e arises from optimizing the trade-off between gathering information (rejecting early candidates) and acting before the best candidate passes. The problem illustrates how optimal stopping often involves a phase transition between exploration and exploitation.