= Solution
For the intended <random walk> model, take $S_0$ to be deterministic, or <independent> of all the <independent and identically distributed random variables> $Y_j=S_j-S_{j-1}$. If $\nu$ is their common <probability distribution>, then $Y_{t+1}$ is <independent> of $\mathcal F_t=\sigma(S_0,Y_1,\ldots,Y_t)$. This supplies the <Markov property> that the backward <dynamic programming> argument needs. Define the <transition operator>
$$
(Ph)(s)=\int_{\mathbb R}h(s+y)\,\nu(dy)
$$
and the deterministic <optimal stopping value function> recursively by
$$
V(T,s)=f(s),\qquad V(t,s)=\max\{f(s),(PV(t+1,\cdot))(s)\}.
$$
At any state where the conditional law is evaluated, <independence> gives
$$
\mathbb E[V(t+1,S_{t+1})\mid\mathcal F_t]=(PV(t+1,\cdot))(S_t).
$$
Backward induction, starting with $U_T=f(S_T)$, proves \b[the intended representation]
$$
\boxed{U_t=V(t,S_t).}
$$
Integrability along the actual <random walk> makes the recursion finite at the states used by that process, up to null sets. If finite real-valued <value functions> on all of $\mathbb R$ are intended, a convenient sufficient convention is statewise integrability: $\mathbb E|f(s+Y_1+\cdots+Y_k)|<\infty$ for every $s$ and $0\leq k\leq T$. Indeed each stopping value is bounded in absolute value by the <expectation> of the sum of the absolute rewards. This convention makes the displayed recursion finite and measurable everywhere; the source only assumes integrability from the given starting process.
The printed independence of the increments alone does not suffice if $S_0$ can reveal future increments. Here is a bounded finite-state counterexample, also with a <convex> reward. Let $T=2$, let $\varepsilon_1,\varepsilon_2$ be <independent> fair signs, and set
$$
S_0=\varepsilon_2,\qquad S_1=\varepsilon_1+\varepsilon_2,
\qquad S_2=\varepsilon_1+2\varepsilon_2,\qquad f(s)=s^+.
$$
The two increments are exactly $\varepsilon_1,\varepsilon_2$, hence <independent and identically distributed>. But $\mathcal F_1$ already knows both signs, so $U_1=\max\{S_1^+,S_2^+\}$. On the two positive-probability histories with $S_1=0$, its values are respectively $0$ and $1$. Thus no deterministic $V(1,0)$ can work. Adding independence of $S_0$ from the increments repairs this missing <Markov property> hypothesis.
Back to article page
