788 CHAPTER 29. MARTINGALES

are identified as unbroken strings of ones for Yk with a zero at each end, with the possibleexception of the last string of ones which may be missing the zero at the upper end andmay or may not 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. In particular,

Y−1k+1 (1) = ([Yk = 1]∩ [Xk < b])∪ ([Yk = 0]∩ [Xk ≤ a])

This set is in F by induction. Of course, Y−1k+1 (0) is just the complement of this set. Thus

Yk+1 is F measurable since 0,1 are the only two values. 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 29.3.5 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

), (29.6)

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

The following is called the upcrossing lemma.

29.3.1 Upcrossings

Lemma 29.3.6 (upcrossing lemma) Let {(Xi,Fi)}ni=1 be a sub-martingale and let

U[a,b] (ω)

be the number of upcrossings of [a,b]. Then

E(U[a,b]

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

b−a.

Proof: Let φ (x) ≡ a+(x−a)+ so that φ is an increasing convex function always atleast as large as a. By Lemma 29.3.2 it follows that {(φ (Xk) ,Fk)} is also a sub-martingale.

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

∑i=k+1

φ (Xi)−φ (Xi−1)