Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 211 / 5

Backward induction makes every $U_t$ adapted and integrable: the conditional expectation of an integrable random variable is integrable, and $|\max (a,b)|\le |a|+|b|$. The Snell envelope recursion directly gives $U_t\ge \mathbb{E}[U_{t+1}\mid {\mathcal{F}}_t]$, so $U$ is a supermartingale.

If $Z$ is a submartingale, iterating its defining inequality gives $\mathbb{E}[Z_T\mid {\mathcal{F}}_t]\ge Z_t$. Starting at $U_T=Z_T$ and applying the tower property of conditional expectation backwards showsThis last conditional expectation is a true martingale. The conclusions areIn the second case waiting until $T$ attains the optimal stopping value. It is not generally true that $U_t=Z_t$: that further equality holds when $Z$ itself is a martingale.

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,\dots ,Y_t)$. This supplies the Markov property that the backward dynamic programming argument needs. Define the transition operatorand the deterministic optimal stopping value function recursively byAt any state where the conditional law is evaluated, independence givesBackward induction, starting with $U_T=f(S_T)$, proves the intended representationIntegrability 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\le k\le 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 ${\epsilon }_1,{\epsilon }_2$ be independent fair signs, and setThe two increments are exactly ${\epsilon }_1,{\epsilon }_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.

Use the random walk interpretation and optimal stopping value function recursion specified in part (b). If $h$ is convex, translating and integrating its convexity inequality gives, for $0<\theta <1$,Thus the transition operator preserves convex functions. Also the pointwise maximum of convex functions is convex: each of two convex functions at an intermediate point is bounded by the same convex combination of their pointwise maximum at the endpoints. Starting with $V(T,\cdot )=f$, backward induction intherefore proves the asserted convexity in the intended model:The statewise integrability convention in part (b) gives finite convex functions on all real states. The same inequality holds for the canonical extended value function wherever the expectations are well-defined. Integrability only along one started process need not make that canonical function finite at unused states: for $T=1$, $S_0=0$, $f(s)=e^{s^2}$ and increment density proportional to $e^{-y^2-|y|}$, $\mathbb{E}f(S_1)<\infty$, but $\mathbb{E}f(s+Y_1)=\infty$ for $s>1/2$. This concerns the canonical recursion away from visited states, rather than the almost-sure identity for $U$. Arbitrary off-state versions of $V$ need not be convex; the recursive version is the one meant here. No zero-mean assumption on the increments was used, and convexity alone does not make $f(S_t)$ a submartingale for an arbitrary drift.