742 CHAPTER 27. ANALYTICAL CONSIDERATIONS

Proof: Let X0 (ω) ≡ a + 1, let Y0 (ω) ≡ 0, and let Yk (ω) remain 0 for k = 0, · · · , luntil Xl (ω) ≤ a. When this happens (if ever), Yl+1 (ω) ≡ 1. Then let Yi (ω) remain 1 fori = l +1, · · · ,r until Xr (ω)≥ b when Yr+1 (ω)≡ 0. Let Yk (ω) remain 0 for k ≥ r+1 untilXk (ω) ≤ a when Yk (ω) ≡ 1 and continue in this way. Thus the upcrossings of Xi (ω) areidentified as unbroken strings of ones with a zero at each end, with the possible exceptionof the last string of ones which may be missing the zero at the upper end and may or maynot be an upcrossing.

Note also that Y0 is measurable because it is identically equal to 0 and that if Yk ismeasurable, then Yk+1 is measurable because the only change in going from k to k+1 is achange from 0 to 1 or from 1 to 0 on a measurable set determined by Xk. Now let

Zk (ω) =

{1 if Yk (ω) = 1 and Yk+1 (ω) = 0,0 otherwise,

if k < n and

Zn (ω) =

{1 if Yn (ω) = 1 and Xn (ω)≥ b,0 otherwise.

Thus Zk (ω) = 1 exactly when an upcrossing has been completed and each Zi is a randomvariable.

U[a,b] (ω) =n

∑k=1

Zk (ω)

so U[a,b] is a random variable as claimed. ■The following corollary collects some key observations found in the above construction.

Corollary 27.3.7 U[a,b] (ω) ≤ the number of unbroken strings of ones in the sequence{Yk (ω)} there being at most one unbroken string of ones which produces no upcrossing.Also

Yi (ω) = ψ i

({X j (ω)

}i−1j=1

), (27.4)

where ψ i is some function of the past values of X j (ω).

Lemma 27.3.8 (upcrossing lemma) Let {Xi}ni=1 be a sub-martingale and suppose

E (|Xn|)< ∞.

Then

E(U[a,b]

)≤ E (|Xn|)+ |a|

b−a.

Proof: Let φ (x)≡ a+(x−a)+. Thus φ is a convex and increasing function.

φ (Xk+r)−φ (Xk) =k+r

∑i=k+1

φ (Xi)−φ (Xi−1)

=k+r

∑i=k+1

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

∑i=k+1

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

The upcrossings of φ (Xi) are exactly the same as the upcrossings of Xi and from 27.4,

E

(k+r

∑i=k+1

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

)