29.3. DISCRETE STOCHASTIC PROCESSES 789

=k+r

∑i=k+1

(φ (Xi)−φ (Xi−1))Yi +k+r

∑i=k+1

(φ (Xi)−φ (Xi−1))(1−Yi).

Observe that Yi is Fi−1 measurable from its construction in Proposition 29.3.4, Yi depend-ing only on X j for j < i.

Now let the unbroken strings of ones for {Yi (ω)} be

{k1, · · · ,k1 + r1} ,{k2, · · · ,k2 + r2} , · · · ,{km, · · · ,km + rm} (29.7)

where m = V (ω) ≡ the number of unbroken strings of ones in the sequence {Yi (ω)}. ByCorollary 29.3.5 V (ω)≥U[a,b] (ω).

φ (Xn (ω))−φ (X1 (ω))

=n

∑k=1

(φ (Xk (ω))−φ (Xk−1 (ω)))Yk (ω)

+n

∑k=1

(φ (Xk (ω))−φ (Xk−1 (ω)))(1−Yk (ω)).

The first sum in the above reduces to summing over the unbroken strings of ones be-cause the terms in which Yi (ω) = 0 contribute nothing. Therefore, observing that forx > a,φ (x) = x,

φ (Xn (ω))−φ (X1 (ω))≥U[a,b] (ω)(b−a)+0+

n

∑k=1

(φ (Xk (ω))−φ (Xk−1 (ω)))(1−Yk (ω)) (29.8)

where the zero on the right side results from a string of ones which does not producean upcrossing. It is here that it is important that φ (x) ≥ a. Such a string begins withφ (Xk (ω)) = a and results in an expression of the form φ (Xk+m (ω))−φ (Xk (ω))≥ 0 sinceφ (Xk+m (ω))≥ a. If Xk had not been replaced with φ (Xk) , it would have been possible forφ (Xk+m (ω)) to be less than a and the zero in the above could have been a negative numberThis would have been inconvenient.

Next take the expectation of both sides in 29.8. This results in

E (φ (Xn)−φ (X1)) ≥ (b−a)E(U[a,b]

)+E

(n

∑k=1

(φ (Xk)−φ (Xk−1))(1−Yk)

)≥ (b−a)E

(U[a,b]

)The reason for the last inequality where the term at the end was dropped is

E ((φ (Xk)−φ (Xk−1))(1−Yk))

= E (E ((φ (Xk)−φ (Xk−1))(1−Yk) |Fk−1))

= E ((1−Yk)E (φ (Xk) |Fk−1)− (1−Yk)E (φ (Xk−1) |Fk−1))

≥ E ((1−Yk)(φ (Xk−1)−φ (Xk−1))) = 0.

Recall that Yk is Fk−1 measurable and that (φ (Xk) ,Fk) is a sub-martingale. ■The reason for this lemma is to prove the amazing sub-martingale convergence theorem.