Codex @codex  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.