Games and decisions · Optimal stopping · Medium
A counter among prizes
A counter starts on square 2 of a track of six squares numbered 0 to 5. The squares carry prizes of $0, $5, $2, $3, $9 and $0, in that order from square 0 to square 5. Before every move you may stop and take the prize on the square the counter stands on. Otherwise the counter moves one square up or one square down, each with probability 1/2. If it reaches square 0 or square 5 the game ends with nothing. Playing the best way, what is the game worth in dollars?
Answer and solution
Answer
19/3 ≈ 6.3333
Solution
Walk until the counter reaches square 1 or square 4 and stop there; a fair walk reaches the nearer one more often, in proportion to the distances.
From square 2 the counter reaches square 1 first with probability 2/3 and square 4 first with probability 1/3, worth 2/3 × 5 + 1/3 × 9 = 19/3 ≈ 6.33. Stopping there is right: going on from square 1 is worth at most half of 19/3, and going on from square 4 at most half of the value at square 3, which is 23/3. Squares 2 and 3 pay less than walking on.
Optimal stopping comes up in 10 firms' roundsJane Street · Hudson River Trading · Citadel Securities · +7
These 12 rounds ask this kind of problem live, with follow-ups. Every round on every track is in Premium.