Consider an optimal stopping problem in which the optimality equation takes the form

$$F_{t}(x)=\max \left\{r(x), E\left[F_{t+1}\left(x_{t+1}\right)\right]\right\}, \quad t=1, \ldots, N-1,$$

$F_{N}(x)=r(x)$, and where $r(x)>0$ for all $x$. Let $S$ denote the stopping set of the onestep-look-ahead rule. Show that if $S$ is closed (in a sense you should explain) then the one-step-look-ahead rule is optimal.

$N$ biased coins are to be tossed successively. The probability that the $i$ th coin toss will show a head is known to be $p_{i}\left(0<p_{i}<1\right)$. At most once, after observing a head, and before tossing the next coin, you may guess that you have just seen the last head (i.e. that all subsequent tosses will show tails). If your guess turns out to be correct then you win $£ 1$.

Suppose that you have not yet guessed 'last head', and the $i$ th toss is a head. Show that it cannot be optimal to guess that this is the last head if

$$\frac{p_{i+1}}{q_{i+1}}+\cdots+\frac{p_{N}}{q_{N}}>1$$

where $q_{j}=1-p_{j}$.

Suppose that $p_{i}=1 / i$. Show that it is optimal to guess that the last head is the first head (if any) to occur after having tossed at least $i^{*}$ coins, where $i^{*} \approx N / e$ when $N$ is large.