Katkat
Back

Optimal Stopping with Square-Number Ruin

Jane StreetSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenStatistics & Math

Last updated

Analyze an optimal stopping game where a player rolls a fair six-sided die to accumulate points but busts if the running sum hits a positive perfect square. Tests dynamic programming, renewal theory intuition, and rigorous edge-case analysis under uncertain stopping boundaries.

Scenario

You are offered a game played with a single fair six-sided die (faces 1 through 6). The game starts with a running sum of S = 0.

On each turn:

  1. You roll the die and add the outcome to your running sum S.
  2. Ruin Condition: If the new sum S is a positive perfect square (S in {1, 4, 9, 16, 25, ...}), you immediately bust. The game ends, and your payout is 0.
  3. Stopping Decision: If S is not a perfect square, you may choose to either stop and bank your current score (receiving a payout equal to S), or roll the die again.

Tasks

1. Dynamic Programming & Value Formulation

  • Define the value function V(s), representing the maximum expected payout achievable from a non-busting state s.
  • State the Bellman optimality equation for V(s).
  • Explain whether the game has a finite or infinite optimal expected payout. In particular, discuss the survival probability of crossing the k-th square as k -> inf.

2. Early-State Evaluation

  • Suppose you take your first roll from S = 0. With probability 2/6, you bust immediately on 1 or 4.
  • For the non-busting initial rolls (S in {2, 3, 5, 6}), determine whether it is optimal to stop immediately or continue rolling. Derive the one-step lookahead comparison and explain any assumptions required to bound future expectations.

3. Asymptotic Policy & Edge Cases

  • As S grows very large, the distance between consecutive squares k^2 and (k+1)^2 expands as 2k + 1. Describe how the optimal policy behaves in the "middle" of a wide interval between two distant squares versus when approaching the next square boundary.
  • How does the optimal policy change if:
    • A bust only resets the score by a fixed penalty rather than setting the total payout to zero?
    • The die has faces 0 to 5 instead of 1 to 6?

Hints

Hint 1

Notice that the probability of hitting any specific integer in a renewal process with average step size 3.5 approaches 1 / 3.5 = 2/7 as the distance from the starting point increases.

Hint 2

Because the probability of hitting a square upon crossing it is roughly bounded away from 0, the probability of surviving n consecutive square crossings decays exponentially, while the reward scales at most quadratically.

Hint 3

For the first roll decision, compare the guaranteed payout of stopping at s in {2, 3, 5, 6} against the expected value of rolling again, noting that from s = 2, you risk busting on 4 (with roll 2) or 9 (impossible in one roll, but reachable later).

Follow-up questions

  • What is the exact asymptotic probability of hitting the square k^2 conditional on surviving past (k - 1)^2 as k becomes arbitrarily large?
  • If you were allowed one 'free pass' (forgiving your first bust), how would that affect your threshold for stopping in the first few intervals?
  • Could this problem be solved numerically using value iteration, and what truncation point S_max would guarantee that the error on V(0) is below 0.01?