= Solution
Let $\nu$ be the common increment law. The <random walk> has the <Markov property>, since $\xi_{t+1}$ is independent of $\mathcal F_t$ and $X_{t+1}=X_t+\xi_{t+1}$. Its <transition operator> is $Ph(x)=\int h(x+z)\nu(dz)$ wherever that integral exists.
Set $V(T,x)=f(x)$. For $1\leq t<T$, suppose the Borel function $V(t+1,\cdot)$ has been constructed and represents $U_{t+1}$. On the Borel set
$$
A_t=\left\{x:\int|V(t+1,x+z)|\nu(dz)<\infty\right\},
$$
define the <optimal stopping value function> recursively by
$$
V(t,x)=\max\left\{f(x),\int V(t+1,x+z)\nu(dz)\right\}.
$$
Outside $A_t$, assign the finite Borel value $f(x)$. Measurability of integrals against a fixed probability law proves measurability of both the set and the function. Integrability of $U_{t+1}=V(t+1,X_t+\xi_{t+1})$ and independence imply $X_t\in A_t$ almost surely and
$$
\mathbb E[U_{t+1}\mid\mathcal F_t]
=\int V(t+1,X_t+z)\nu(dz).
$$
The Snell recursion thus proves $U_t=V(t,X_t)$ by induction.
At time zero the generated <sigma-algebra> is trivial, so $U_0$ is deterministic. Since $X_0=0$, define $V(0,x)=U_0$ for all $x$, with
$$
U_0=\max\{f(0),\mathbb E[V(1,\xi_1)]\}
$$
when $T\geq1$. This supplies a globally finite deterministic representation without assuming integrability of rewards from every unvisited starting state. Hence
$$
\boxed{U_t=V(t,X_t)\quad(0\leq t\leq T).}
$$
With the additional statewise integrability normally used to define a value function for arbitrary starting states, one can instead use the Bellman maximum at time zero too. For $T=0$, the representation is simply $U_0=f(0)$.
Back to article page
