Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 39 / 3 / b / 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\le t<T$, suppose the Borel function $V(t+1,\cdot )$ has been constructed and represents $U_{t+1}$. On the Borel setdefine the optimal stopping value function recursively byOutside $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 andThe 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$, withwhen $T\ge 1$. This supplies a globally finite deterministic representation without assuming integrability of rewards from every unvisited starting state. HenceWith 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)$.