Optimal Stopping in Dice Game

This interview question introduces a simple dice game with a probabilistic stopping rule, and asks for the expected total payout accumulated over the course of play. The setup emphasizes a process that evolves in discrete steps, with the continuation or termination decided by the random outcome of each step. Candidates must reason about a payoff that is itself random both in size and in duration, because the number of dice rolls is not fixed in advance but determined by the game's rules. This style of question is common in quantitative interviews for roles that work with stochastic processes and stopping rules, such as certain trading and quantitative research positions.

To tackle the problem, candidates are expected to recognize the structure of a sum of independent, identically distributed increments observed up to a random stopping time. The key ideas include linearity of expectation, independence assumptions, and the proper use of Wald's equality or an equivalent argument based on expected number of steps times expected payoff per step. Interviewers watch for clear identification of the stopping time, correct conditioning on the game's continuation, and an ability to justify any interchange of expectation and summation without relying on ad hoc recursion.

What it tests

When analyzing stochastic processes with random stopping times, the key insight is that the expected total of a sum of independent, identically distributed random variables up to a stopping time can be decomposed into the product of the expected number of steps and the expected value per step. This is formalized by Wald's Equality, which holds when the stopping time is independent of the future and certain regularity conditions are met. The principle holds because, on average, the process does not "anticipate" its own end: the expected contribution from each step remains constant, and the randomness in the number of steps is captured entirely by the expected stopping time. This approach allows us to sidestep complicated recursive calculations by focusing on the linearity of expectation and the independence structure. The power of this principle is that it reduces the problem to computing two simpler expectations: one for the step and one for the count.