Threshold Strategies

Hard5–6 hrsOptimal StoppingThresholdExpected ValueBellman EquationJane Street

Overview

Threshold strategies are optimal for any i.i.d. sequential sampling problem with replacement: at every draw, you compare the current value to a fixed threshold τ and stop if and only if the current draw exceeds τ. The threshold equals the NET continuation value — the expected prize you'd get if you kept playing forever, minus the expected cost. The derivation: write total value V(τ) as a function of τ, differentiate, set to zero. The elegant self-consistency: the optimal threshold is exactly the value of the game rounded up to the nearest integer. This makes sense: stop when the current draw beats your outside option (keeping playing).

How to Recognize

→Draw from a distribution (with or without replacement) and decide to stop
→'What is the optimal strategy?' or 'what is the fair value of this game?'
→Game involves a cost per round and a prize equal to the last accepted value
→Sampling continues until you 'accept' — with replacement problems
→Keywords: 'play as many rounds as you want', 'each round costs X'

Step-by-Step Approach

1.With replacement: threshold τ is the SAME every round (stationary problem)
2.V(τ) = E[prize | X ≥ τ] − (cost per draw) × E[# draws to get X ≥ τ]
3.E[prize | X ≥ τ] = (τ + max) / 2 for discrete uniform
4.E[# draws] = 1/P(X ≥ τ) since each draw is geometric
5.Optimize V(τ) analytically: dV/dτ = 0, then verify it's a maximum

Key Formulas

V(\tau) = \frac{\tau + x_{\max}}{2} - \frac{c}{P(X \ge \tau)}

\tau^* = x_{\max} + 1 - \sqrt{\frac{2c \cdot (x_{\max}+1-x_{\min})}{1}} \approx x_{\max} - \sqrt{2c\,n}

\text{Picking Hat: } \tau^* = 87,\quad V^* = \tfrac{1209}{14} \approx \

86.36$

\text{Self-consistency: stop if } X > V^*

(threshold

= \lceil V^* \rceil

)

Worked Examples

0Quick Example

Hat 1–100, cost

1/draw: V(τ) = (τ+100)/2 − 100/(101−τ). Set dV/dτ=0: (101−τ)²=200 → τ*=87. V(87) = 93.5 − 50/7 ≈

86.36.

Problem

A hat contains the numbers 1–100. Each round, AJ draws a number (with replacement), writes it down, and pays $1. The prize is the last number written. With optimal play, what is the fair value of this game?

Solution

STRATEGY STRUCTURE: Since draws are i.i.d. (with replacement), the optimal strategy is a threshold τ: stop if and only if current draw ≥ τ.

VALUE FUNCTION: P(stop each round) = (101−τ)/100. Expected # draws = 100/(101−τ). E[prize | stop] = mean of {τ, τ+1, ..., 100} = (τ+100)/2.

V(τ) = (τ+100)/2 − 1 × 100/(101−τ) = (τ+100)/2 − 100/(101−τ).

OPTIMIZE: dV/dτ = 1/2 − 100/(101−τ)² = 0 → (101−τ)² = 200 → 101−τ = 10√2 ≈ 14.14 → τ* ≈ 86.86.

ROUND to integer: compare V(86) and V(87).

V(86) = 186/2 − 100/15 = 93 − 20/3 ≈ 86.33.

V(87) = 187/2 − 100/14 = 93.5 − 50/7 = 1209/14 ≈ 86.36.

V(88) = 188/2 − 100/13 = 94 − 100/13 ≈ 86.31.

Optimal τ* = 87. SELF-CONSISTENCY CHECK: V ≈ 86.36 < 87 = τ* ✓ (stop when draw exceeds current value).

Answer

$V^* = \frac{1209}{14} \approx \$ 86.36 $. Strategy: draw until X ≥ 87. On average, draw$ \approx 7.1 $times. Expected prize ≈$ 93.50. Expected cost ≈ $7.14.

Common Mistakes

!
Using the WRONG threshold: the threshold is ⌈V*⌉, not E[X] or max/2 or any other naive guess.
!
Forgetting the per-draw COST when computing continuation value. More costs → lower V → lower threshold → stop sooner.
!
For WITHOUT-replacement problems: the distribution changes each draw (state is what's been seen), so a single static threshold is NOT optimal — you need to update.
!
Checking only integer thresholds without deriving the continuous optimum first. Always differentiate, find τ_continuous, then check τ_floor and τ_ceil.
!
Misidentifying the problem type: if it says 'with replacement', use static threshold. If 'without replacement', use backwards induction.

Practice Problems

Click "Show Answer" to reveal

A hat has numbers 1–6 (uniform, with replacement). Each draw costs $0.25. What is the optimal threshold and expected value?

Hint: V(τ) = (τ+6)/2 − 0.25 × 6/(7−τ). Differentiate: dV/dτ = 1/2 − 0.25×6/(7−τ)² = 0 → (7−τ)² = 3 → τ* = 7−√3 ≈ 5.27.

Same hat (1–6) but NOW each draw costs $1 (expensive!). What changes?

Hint: V(τ) = (τ+6)/2 − 1 × 6/(7−τ). Optimize. The high cost means you want to stop quickly — threshold will be lower.

You're playing a game: draw uniformly from [0,1] (continuous), costs $c per draw, with replacement. What is the optimal threshold τ* and expected value V*?

Hint: V(τ) = E[X | X>τ] − c/P(X>τ) = (1+τ)/2 − c/(1−τ). Differentiate with respect to τ.

Back to Study Plan

Solving Recurrences Analytically The Secretary Problem