Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've got a very basic question about optimal stopping. It may have just been me, but I feel like my professor didn't do a great job of explaining the topic too well. I was hoping one of you would be able to step me through this simple example:

Consider a simple random walk with absorbing boundaries on {0, 1, 2, ..., 10}. Suppose the following payoff function is given

$$[0, 2, 4, 3, 10, 0, 6, 4, 3, 3, 0].$$

Find the optimal stopping rule and give the expected payoff starting at each site.

Any help is greatly appreciated. Thanks!

share|improve this question
Reference: This is Exercise 4.1 (page 98) in Gregory Lawler's "Introduction to Stochastic Processes (2nd edition)". –  Byron Schmuland Apr 25 '14 at 22:56

1 Answer 1

Clearly you should stop at $4$, with value $10$, and have to stop at $0$ or $10$ with value $0$. We can decompose this into two games, $[0,2,4,3,10]$ and $[10,0,6,4,3,3,0]$ Taking the first, we should play at $3$ as we gain either way. On average, we can't lose playing at $1$. Letting $a,b,c$ be the values of $1,2,3$ we have $a=\frac b2, b=\max(4, \frac {a+c}2), c=5+\frac b2$. So $b=\max (4,\frac {5+b}2)\ge \frac 92$, so we should play at $2, b=5, a=\frac 52, c=\frac {15}2$, and the expected payoff is $[0,\frac 52,5,\frac {15}2,10]$ with a stopping rule of only stop at $0$ and $4$. The fact that the expectations are linear in position reflects that we never stop midway. The second is similar.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.