# Optimal Stopping Example

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!

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

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.