Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 39 / 3

Backward induction first proves that the Snell envelope is adapted and integrable. At each step, $|U_t|\le |Y_t|+\mathbb{E}[|U_{t+1}|\mid {\mathcal{F}}_t]$, so integrability follows from that of $Y_t$ and $U_{t+1}$. Its defining maximum immediately giveswhich proves that $U$ is a supermartingale.

If $Y$ is a submartingale, the sharper backward identity isIt holds at $T$. If it holds at $t+1$, the tower property of conditional expectation gives $\mathbb{E}[U_{t+1}\mid {\mathcal{F}}_t]=\mathbb{E}[Y_T\mid {\mathcal{F}}_t]$. Iterating the submartingale inequalities shows that this is at least $Y_t$, so the maximum chooses this continuation value. The displayed identity then makes $U$ a martingale.

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)$.

The key convexity calculation is that the random-walk transition operator preserves convex functions. If $h$ is convex, then for $0<\theta <1$,The pointwise maximum of convex functions is convex as well: the convexity inequality holds for each candidate and is bounded above by the convex combination of the two endpoint maxima. Thus the Bellman recursion proves convexity of a random-walk Snell value function by backward induction from $V(T,\cdot )=f$.

To ensure that the functions in this argument are genuinely finite, rather than silently imposing a growth bound on $f$, use integrability of translated convex random-walk rewards. Write $Z_j$ for a sum of $j$ independent increments with the same law. For $j\le T-1$, the assumptions give integrability of $f(Z_j)$ and $f(Z_{j+1})$. The negative part of a finite convex function is Lipschitz, so translating $Z_j$ preserves integrability of the negative part. For the positive part and $x>0$, if the increment law is unbounded above, take an independent increment $\eta$ and $p=\mathbb{P}(\eta \ge x)>0$. On that event $Z_j+x$ lies between $Z_j$ and $Z_j+\eta$, so convexity givesIf increments are bounded above by $M$, then $Z_j\le jM$ and the same convexity argument between $Z_j$ and $jM+x$ bounds the positive part by $f(Z_j{)}^{+}+f(jM+x{)}^{+}$. For $x<0$, use the corresponding lower-tail argument. Thus every translated reward $f(x+Z_j)$ is integrable for $j\le T-1$.

For $t\ge 1$, backward induction also gives the boundIt justifies every convolution in the Bellman recursion at these times, so the arbitrary assignments outside $A_t$ in the previous part are never needed when $f$ is convex. The displayed convexity calculation therefore proves that each $V(t,\cdot )$ for $t\ge 1$ is a finite convex function. The chosen $V(0,\cdot )=U_0$ is constant and hence convex. This proves the requested conclusion for the deterministic representation under the finite-horizon assumptions.

There is a distinction between this representation and a value function for every possible starting point at time zero. Without translated integrability at the full horizon, the latter may take $+\infty$ at unused states. For example, with $T=1$, $f(x)=e^{x^2}$ and $\mathbb{P}({\xi }_1=k)=c{e}^{-k^2-k}$ for $k=1,2,\dots$, the observed reward is integrable, but $\mathbb{E}[f(x+{\xi }_1)]=c{e}^{x^2}{\sum }_{k\ge 1}{e}^{(2x-1)k}$ is infinite for $x\ge 1/2$. The constant time-zero extension avoids claiming a globally finite Bellman function under insufficient assumptions. If integrability is assumed for all times of an infinite random walk, the translated-reward argument with one extra time also makes the full time-zero Bellman function finite and convex.