Compute optimal stopping in a die-rolling game
Capital OneData Scientist · Technical ScreenLast updated
This question evaluates a candidate's grasp of optimal stopping theory, expected value computation, and finite-horizon decision-making under uncertainty, including recognition of threshold-based policies and backward-induction reasoning relevant to data scientist roles.
Consider three sequential die-rolling games with a fair six-sided die (pips 1–6). You may observe each roll and decide whether to stop and take the shown value in dollars. If you have not stopped before the last allowed roll, you must take the last roll’s value. Game A: Up to three rolls, no costs. Find the optimal stopping policy and exact expected payoff. Game B: Up to three rolls; if you choose to continue after roll 1 or roll 2, you must pay $1 before rolling again (each continuation costs $1). Find the optimal stopping thresholds and exact expected payoff. Game C: Up to three rolls; the second and third rolls each require paying $1 to roll (i.e., you always pay $1 to access roll 2 if you continue from roll 1, and another $1 to access roll 3 if you continue from roll 2). Find the optimal policy and expected payoff. Bonus: Generalize Game B to an n-sided die with faces 1..n and a continuation cost c; derive the stopping threshold(s) as a function of n and c.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.