Quantitative trading interviews at top firms like Jane Street are renowned for their challenging puzzles and mathematical rigor. One classic category of these questions is the “optimal stopping problem,” often illustrated by the marbles problem. This article will comprehensively dissect the Jane Street Quantitative Trader Interview Question: Optimal Stopping Problem with Marbles, breaking down the mathematical concepts, step-by-step solutions, and the logic behind the optimal stopping rule. Whether you are preparing for a quant interview or simply curious about decision theory, this deep dive will illuminate the principles and strategies involved.

Jane Street Quantitative Trader Interview Question: Optimal Stopping Problem with Marbles

Understanding the Problem Statement

Let’s begin by precisely stating the version of the problem we will solve:

• You are presented with a bag containing N marbles.
• Each marble has a known payoff value, revealed only when drawn.
• You may draw marbles sequentially, one at a time, and after each draw, you can either stop and accept the current payoff, or continue drawing.
• If you reach the last marble, you must accept its payoff.
• Goal: Formulate and solve for the optimal stopping rule (i.e., when should you stop to maximize your expected payoff?), and compute the expected value when following this rule.

This is a classic example of an optimal stopping problem, a type of decision problem in probability theory and statistics.

Optimal Stopping Problem: Concepts and Theory

What is an Optimal Stopping Problem?

An optimal stopping problem is a mathematical exercise in sequential decision-making. You observe a sequence of random variables and must choose a stopping time (i.e., a rule that tells you when to stop) to maximize or minimize an expected value. These problems arise in areas such as finance (e.g., American options), hiring (secretary problems), and, as in this case, interview puzzles.

Key Concepts Involved

• Stopping Time: A rule that tells you, based on the information observed so far, whether to stop or continue at each step.
• Payoff Sequence: The set of values associated with each marble, usually assumed to be random variables from a known distribution.
• Expected Value: The average payoff you can achieve by following a particular stopping rule.
• Dynamic Programming / Backward Induction: Techniques used to recursively compute the optimal expected payoff and stopping rule.

Formulating the Marbles Optimal Stopping Problem

Let’s formalize the setup mathematically.

Model Assumptions

• There are N marbles, labeled \( 1, 2, \ldots, N \).
• The payoff of marble \( i \) is a random variable \( X_i \), drawn independently from a known distribution \( F \).
• You observe the payoff \( X_i \) after drawing marble \( i \), and then decide whether to stop (and receive \( X_i \)) or continue to the next marble.
• If you reach marble \( N \), you must accept \( X_N \).

Objective

Find the optimal stopping rule that maximizes your expected payoff, and determine the expected value under this rule.

Mathematical Formulation

Defining the Value Function

Let’s define \( V_n \) as the expected payoff you can achieve when there are \( n \) marbles left (i.e., you are about to draw the next marble, and there are \( n \) in total to choose from).

Here is the recursive relationship:

• \( V_n \): Optimal expected payoff with \( n \) marbles left (before drawing the next marble).
• \( X_n \): Payoff of the marble drawn at this step (random variable).
• \( V_{n-1} \): Optimal expected payoff if you skip the current marble and continue with \( n-1 \) marbles.

The base case is:

because if only one marble remains, you must accept its value.

Solving the Problem: Backward Induction

Step 1: Base Case

For the last marble (\( n = 1 \)):

Step 2: Recursive Step

For \( n > 1 \), the recurrence is:

This means: after observing \( X_n \), you should stop and take \( X_n \) if it is at least as good as the expected payoff from continuing, otherwise you should continue.

Step 3: Threshold Rule

Define the stopping threshold at step \( n \) as \( V_{n-1} \). After observing \( X_n \):

• If \( X_n \geq V_{n-1} \), you stop and collect \( X_n \).
• If \( X_n < V_{n-1} \), you continue to the next marble.

Therefore, the optimal stopping rule is: Stop at the first marble whose value is at least as large as the expected value of continuing.

Analytical Solution for Known Distributions

To proceed further, we need to specify the distribution of payoffs. The solution method applies to any distribution, but for clarity, let's assume each \( X_i \) is drawn independently from the uniform distribution over [0,1], i.e., \( X_i \sim \text{Uniform}(0,1) \).

Uniform[0,1] Case

Let’s derive \( V_n \) for each \( n \) using backward induction.

Base Case: \( n = 1 \)

Recursive Step: \( n > 1 \)

Suppose that after \( n-1 \) steps, \( V_{n-1} \) is known. At the \( n \)-th draw, you observe \( X_n \):

Because \( X_n \sim \text{Uniform}(0,1) \), this can be written as:

Split the integral at \( x = V_{n-1} \):

Calculate each part:

• \( \int_{0}^{V_{n-1}} V_{n-1}\, dx = V_{n-1} \cdot V_{n-1} = V_{n-1}^2 \)
• \( \int_{V_{n-1}}^{1} x\, dx = \left[ \frac{x^2}{2} \right]_{V_{n-1}}^{1} = \frac{1}{2} - \frac{V_{n-1}^2}{2} \)

Add them:

Final Recursion Formula:

with \( V_1 = \frac{1}{2} \).

Explicit Solution for Small N

Let’s compute \( V_n \) for small \( n \):

• n = 1:
  \( V_1 = \frac{1}{2} \)
• n = 2:
  \[ V_2 = \frac{1}{2} \left( \left( \frac{1}{2} \right)^2 + 1 \right) = \frac{1}{2} \left( \frac{1}{4} + 1 \right) = \frac{1}{2} \cdot \frac{5}{4} = \frac{5}{8} = 0.625 \]
• n = 3:
  \[ V_3 = \frac{1}{2} \left( (0.625)^2 + 1 \right) = \frac{1}{2} \left( 0.390625 + 1 \right) = \frac{1}{2} \cdot 1.390625 = 0.6953125 \]
• n = 4:
  \[ V_4 = \frac{1}{2} \left( (0.6953125)^2 + 1 \right) = \frac{1}{2} \left( 0.483463 + 1 \right) = \frac{1}{2} \cdot 1.483463 = 0.741731 \]

As \( n \) increases, \( V_n \) approaches 1, but never quite reaches it.

General Properties & Asymptotic Behavior

For large \( n \), the expected value \( V_n \) approaches 1. Intuitively, with more marbles to choose from, you can wait for higher payoffs.

You can show that \( 1 - V_n \) decreases rapidly with \( n \). Specifically, for Uniform[0,1], as \( n \to \infty \):

where \( c \) is a constant. This is related to the famous “secretary problem,” but with known payoff distributions instead of rank order.

Numerical Implementation

Let’s see how you might compute \( V_n \) in practice using Python.

def compute_Vn_uniform(n):
    V = 0.5
    for i in range(2, n+1):
        V = 0.5 * (V**2 + 1)
    return V

for n in range(1, 11):
    print(f"n={n}, V_n={compute_Vn_uniform(n):.4f}")

You can extend this code for any \( n \), and for any distribution (using numerical integration for the expectation).

Optimal Stopping Rule: Intuitive Explanation

At each step, you compare the observed marble’s value \( x \) to the expected value of continuing, \( V_{n-1} \).

• If \( x \geq V_{n-1} \), stop and accept \( x \).
• If \( x < V_{n-1} \), continue to the next marble.

This is called a threshold rule. The threshold decreases as you proceed (since fewer marbles remain, the expected future value drops). Early on, you can be picky and wait for high values; later, you must accept lower values.

Relation to Secretary Problem and Insights for Interviews

This “marbles” optimal stopping problem is closely related to the secretary problem (also known as the marriage problem), but with a key difference: in the secretary problem, only the rank of each candidate is revealed, not the value; here, the underlying payoffs are known and drawn from a distribution.

Interviewers at Jane Street and other quant firms use such problems to test:

• Your ability to model and formalize a problem mathematically.
• Your understanding of expectation, recursion, and stopping rules.
• Your intuition about dynamic programming and backward induction.
• Your ability to reason about probability and make optimal decisions under uncertainty.

Generalization: Other Distributions

If marbles are drawn from an arbitrary distribution \( F \) with density \( f(x) \), the recursion becomes:

import matplotlib.pyplot as plt

def compute_Vn_sequence(n_max):
    V_list = [0.5]
    for n in range(2, n_max + 1):
        V_next = 0.5 * (V_list[-1] ** 2 + 1)
        V_list.append(V_next)
    return V_list

n_max = 20
V_seq = compute_Vn_sequence(n_max)
plt.plot(range(1, n_max+1), V_seq, marker='o')
plt.xlabel('Number of Marbles (n)')
plt.ylabel('Expected Payoff V_n')
plt.title('Expected Value vs. Number of Marbles (Uniform[0,1])')
plt.grid(True)
plt.show()